> For the complete documentation index, see [llms.txt](https://twchen.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://twchen.gitbook.io/leetcode/construct-binary-tree-from-preorder-and-postorder-traversal.md).

# Construct Binary Tree from Preorder and Postorder Traversal

## Description

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals `pre` and `post` are distinct positive integers.

**Example 1:**

```
Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
```

**Note:**

* `1 <= pre.length == post.length <= 30`
* `pre[]` and `post[]` are both permutations of `1, 2, ..., pre.length`.
* It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

## Solutions

### Intuitive recursive solution

```cpp
class Solution {
public:
    TreeNode *constructFromPrePost(vector<int> &pre, vector<int> &post) {
        int n = pre.size();
        vector<int> hash(n + 1);
        for (int i = 0; i < n; ++i)
            hash[post[i]] = i; // post is a permutation of [1,2,...,n]
        return helper(pre, 0, n - 1, post, 0, n - 1, hash);
    }
    
    // build a binary tree from pre[l1..r1] and post[l2..r2]
    TreeNode *helper(vector<int> &pre, int l1, int r1,
                     vector<int> &post, int l2, int r2,
                     vector<int> &hash) {
        if (l1 > r1)
            return nullptr;
        auto root = new TreeNode(pre[l1]);
        if (l1 == r1)
            return root;
        int lrv = pre[l1 + 1]; // left root val
        int lri = hash[lrv];   // index of lrv in post
        int nl = lri - l2 + 1; // number of nodes in left sub-tree
        root->left = helper(pre, l1 + 1, l1 + nl,
                            post, l2, lri,
                            hash);
        root->right = helper(pre, l1 + nl + 1, r1,
                             post, lri + 1, r2 - 1,
                             hash);
        return root;
    }
};
```

### Another recursive solution

Credit: [LeetCode Discussion](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161268/C++JavaPython-One-Pass-Real-O\(N\))

```cpp
class Solution {
public:
    TreeNode *constructFromPrePost(vector<int> &pre, vector<int> &post) {
        int i = 0, j = 0;
        return constructFromPrePost(pre, post, i, j);
    }

    /**
     * construct a binary tree starting from pre[i] and post[j]
     * update i and j to the indices of elements that are not used.
     * e.g.,
     * input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1], i = 1, j = 0
     * output: the tree constructed from pre = [2,4,5], post = [4,5,2], i.e.,
     *            2
     *           / \
     *          4   5
     *         i is updated to 4, i.e., pointing to 3
     *         j is updated to 3, i.e., pointing to 6
     */
    TreeNode *constructFromPrePost(vector<int> &pre, vector<int> &post, int &i, int &j) {
        // pre[i] must be the root node
        auto root = new TreeNode(pre[i++]);
        if (root->val != post[j]) // post[j] is not the root node, must belong to the left sub-tree
            root->left = constructFromPrePost(pre, post, i, j);
        if (root->val != post[j]) // post[j] is not the root node, must belong to the right sub-tree
            root->right = constructFromPrePost(pre, post, i, j);
        // post[j] must be the root node, i.e., root-val == post[j]
        ++j;
        return root;
    }
};
```

### Iterative solutions

```cpp
class Solution {
public:
    TreeNode *constructFromPrePost(vector<int> &pre, vector<int> &post) {
        TreeNode dummy(0);
        stack<TreeNode *> st;
        st.push(&dummy);
        int j = 0, n = pre.size();
        for (int i = 0; i < n || j < n; ++i) {
            if (i < n)
                st.push(new TreeNode(pre[i]));
            while (j < n && st.top()->val == post[j]) {
                auto node = st.top();
                st.pop();
                if (st.top()->left != nullptr)
                    st.top()->left = node;
                else
                    st.top()->right = node;
                ++j;
            }
        }
        return dummy.left;
    }
};
```

Credit: [LeetCode Discussion](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161268/C++JavaPython-One-Pass-Real-O\(N\)/209048)

```cpp
class Solution {
public:
    TreeNode *constructFromPrePost(vector<int> &pre, vector<int> &post) {
        stack<TreeNode *> st;
        auto root = new TreeNode(pre[0]);
        st.push(root);
        for (int i = 1, j = 0; i < pre.size(); ++i) {
            // finished constructing the sub-tree rooted at post[j]
            while (st.top()->val == post[j]) {
                st.pop();
                ++j;
            }
            // constructing sub-trees of st.top()
            auto node = new TreeNode(pre[i]);
            if (st.top()->left == nullptr)
                st.top()->left = node;
            else
                st.top()->right = node;
            st.push(node);
        }
        return root;
    }
};
```

There may not be a unique binary tree given the preorder and postorder traversal results.

The reason is that if there is a node with exactly one child, the preorder and postorder traveral results won't change if we swap the child to another sub-tree.

These solutions always put single children to left sub-trees.