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

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

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

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

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.