Construct Binary Tree from Preorder and Postorder Traversal

We can simply run a recursive function to build the tree, realizing that:

• preorder chooses the nodes from root -> left -> right
• postorder chooses the nodes from left -> right -> root

Since preorder processes the root node first, it means that any child node of the root node must be located after the root node in preorder. However, not all nodes located after the root node are children of it; we can determine when the subtree is complete using the postorder array.

Keeping track of the index in preorder using preIndex and postorder using postIndex, we first check if the node value preorder[preIndex] == postorder[postIndex].

• if it is, then we know that the node is a leaf node, and can increment postIndex before breaking.
• if it is not, then we know that the node has children, and can recursively build the left subtree first, before the right subtree (remembering to check if preorder[preIndex] == postorder[postIndex])

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
int preIndex = 0;
int posIndex = 0;
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        TreeNode* root = new TreeNode(preorder[preIndex++]);
        if (root->val != postorder[posIndex]) {
            root->left = constructFromPrePost(preorder, postorder);
        }
        if (root->val != postorder[posIndex]) {
            root->right = constructFromPrePost(preorder, postorder);
        }
        ++posIndex;
        return root;
    }
};

complexity

• Time: O(n)
• Space: O(n)