🏆 Preorder & Postorder | 🥇 Beats 100% | ✨ Most Efficient & Readable | ✔ Explained | C++
\uD83C\uDFC6 Preorder & Postorder | \uD83E\uDD47 Beats 100% | \u2728 Most Efficient & Readable | \u2714 Explained | C++\n\n\n\n# Intuition\nTo solve this proble
# \uD83C\uDFC6 Preorder & Postorder | \uD83E\uDD47 Beats 100% | \u2728 Most Efficient & Readable | \u2714 Explained | C++\n\n![Leetcode100.jpg](https://assets.leetcode.com/users/images/10a95fa9-5b51-4478-b204-32139769c4e4_1729928281.178858.jpeg)\n\n# Intuition\nTo solve this problem **efficiently**, we need to determine the `height` of the binary tree after removing the subtree rooted at each node specified in the **queries** array. Since the queries are independent, **the original tree structure is restored** after each query.\n\nOur approach leverages the properties of `preorder` and `postorder` traversals. By `storing heights at each node` in both traversal orders, we can **quickly** calculate the **height** of the tree after removing each subtree.\n\n# Approach\n1. `Traversals:`\n    - Performing both **preorder** and **postorder** traversals, which helps **store heights** for each node **efficiently**.\n\n2. `Pre-calculated Heights:`\n    - For each node, storing the **maximum height** reached in both traversals.\n\n3. `Efficient Query Processing:`\n    - Using the stored heights for **quick lookups** in response to each query, giving us **constant-time complexity per query**.\n\n# Complexity\n- `Let:`\n    - $$m = nbNodes$$.\n    - $$n = nbQueries$$.\n    - $$MAX\\_VALUE = 100,001$$.\n\n- `Time complexity:` $$O(m + n)$$.\n\n- `Space complexity:` $$O(MAX\\_VALUE)$$.\n\n# Code\n```cpp []\n#define MAX_VALUE 100001\n\n#pragma GCC target("avx, mmx, sse2, sse3, sse4")\n#pragma GCC optimize("Ofast,no-stack-protector")\n\nstatic const int disableSync = [](void) noexcept -> int\n{\n    std::cin.tie(nullptr);\n    std::cout.tie(nullptr);\n    std::ios::sync_with_stdio(false);\n    return 0;\n}();\n\nusing NodeBT_t = TreeNode;\n\nclass Solution final\n{\nprivate:\n    int maxHeight;\n    std::array<int, MAX_VALUE> preorderHeights, postorderHeights;\n\npublic:\n    std::vector<int> treeQueries(const NodeBT_t* const root, std::vector<int>& queries) noexcept\n    {\n        this->setHeights(root);\n        for (int& query : queries)\n            query = std::max(this->preorderHeights[query], this->postorderHeights[query]);\n        return queries;\n    }\n\nprivate:\n    inline void setHeights(const NodeBT_t* const root) noexcept\n    {\n        this->maxHeight = 0;\n        this->setPreorderHeights(root, 0);\n        this->maxHeight = 0;\n        this->setPostorderHeights(root, 0);\n    }\n\n    void setPreorderHeights(const NodeBT_t* const root, const int height) noexcept\n    {\n        if (!root)\n            return;\n        this->preorderHeights[root->val] = this->maxHeight;\n        this->maxHeight = std::max(this->maxHeight, height);\n        this->setPreorderHeights(root->left, height + 1);\n        this->setPreorderHeights(root->right, height + 1);\n    }\n\n    void setPostorderHeights(const NodeBT_t* const root, const int height) noexcept\n    {\n        if (!root)\n            return;\n        this->postorderHeights[root->val] = this->maxHeight;\n        this->maxHeight = std::max(this->maxHeight, height);\n        this->setPostorderHeights(root->right, height + 1);\n        this->setPostorderHeights(root->left, height + 1);\n    }\n};\n```\n\n![Upvote.jpeg](https://assets.leetcode.com/users/images/75c63d89-115f-4092-9a20-32016b22768b_1729928435.2164698.jpeg)
['Array', 'Tree', 'Depth-First Search', 'Recursion', 'C', 'Binary Tree', 'C++']