algoadvance

Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal

Problem Statement

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Clarifying Questions

  1. Are there any constraints on the elements of inorder and postorder?
    • They represent the traversal sequences of a binary tree nodes where each value is unique.
  2. Can the input arrays be empty?
    • Yes, and in this case, the output should be a null reference for the tree.
  3. Can we assume the valid traversal sequences are always provided?
    • Yes, we can assume that the given inorder and postorder sequences form a valid binary tree.

Strategy

  1. Understanding Tree Reconstruction:
    • The last element of the postorder array is the root of the tree.
    • Using this root, we can split the inorder array into left and right subtrees.
    • Recursively do the same for left and right subtrees.
  2. Steps to Solve:
    • Use a map to record the indices of elements in the inorder array for quick access.
    • Create a recursive function to construct the tree using current boundaries of the inorder and postorder arrays.
    • In each recursion, pick the current root from the end of the postorder array segment, find its position in the inorder array to split the tree, and recursively build the left and right subtrees.

Code

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

// 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:
    unordered_map<int, int> inorder_map;

    TreeNode* buildTreeHelper(vector<int>& inorder, vector<int>& postorder, int in_left, int in_right, int& post_index) {
        // Base case
        if (in_left > in_right) {
            return nullptr;
        }
        
        // Get the current root value
        int root_val = postorder[post_index--];
        TreeNode* root = new TreeNode(root_val);
        
        // Root splits inorder list into left and right subtrees
        int index = inorder_map[root_val];
        
        // Build right subtree first as postorder is traversed from back
        root->right = buildTreeHelper(inorder, postorder, index + 1, in_right, post_index);
        root->left = buildTreeHelper(inorder, postorder, in_left, index - 1, post_index);
        
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for (int i = 0; i < inorder.size(); ++i) {
            inorder_map[inorder[i]] = i;
        }
        int post_index = postorder.size() - 1;
        return buildTreeHelper(inorder, postorder, 0, inorder.size() - 1, post_index);
    }
};

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI