Construct Binary Tree from Preorder and Postorder Traversal

Leetcode Problem:

• Construct Binary Tree from Preorder and Postorder Traversal

Summary

• Given two integer arrays, preorder and postorder, where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

Approach

• The approach used is to use a recursive function traversal to construct the binary tree
• The function takes the current node, preorder array index, postorder array index, and the preorder and postorder arrays as parameters
• It creates a new node with the value at the current preorder index, and then recursively constructs the left and right subtrees using the postorder array indices.

Complexity

• O(n) where n is the number of nodes in the tree, since each node is visited once.

Explanation

• The solution uses a recursive function traversal to construct the binary tree
• The function takes the current node, preorder array index, postorder array index, and the preorder and postorder arrays as parameters
• It creates a new node with the value at the current preorder index, and then recursively constructs the left and right subtrees using the postorder array indices
• The base case for the recursion is when the preorder index is greater than or equal to the length of the preorder array, in which case the function returns null
• The function also checks if the current node value matches the current postorder index, and if so, increments the postorder index
• The function then recursively constructs the left and right subtrees, and finally returns the constructed node.

Solution 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 {
    
public:
    
    TreeNode* traversal(TreeNode* root, vector& preorder, int& preIdx, vector& postorder, int& posIdx){
        if(preIdx >= preorder.size()) return nullptr;
        root = new TreeNode(preorder[preIdx]);

        if(root->val == postorder[posIdx]){
            posIdx++;
            return root;
        }

        ++preIdx;
        root->left = traversal(root->left, preorder, preIdx, postorder, posIdx);
        if(root->left == nullptr){
            preIdx--;
        }
        if(root->val == postorder[posIdx]){
            posIdx++;
            return root;
        }
        ++preIdx;
        root->right = traversal(root->right, preorder, preIdx, postorder, posIdx);
        if(root->left == nullptr){
            preIdx--;
        }
        if(root->val == postorder[posIdx]){
            posIdx++;
        }
        return root;
    }
    TreeNode* constructFromPrePost(vector& preorder, vector& postorder) {
        int preIdx = 0;
        int posIdx = 0;
        return traversal(nullptr, preorder, preIdx, postorder, posIdx);
    }
};