889: Construct-Binary-Tree-from-Preorder-and-Postorder-Traversal
Medium

table of contents

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

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].

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