[Leetcode] 106. Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

Given two integer arrays inorderand postorderwhere inorderis the inorder traversal of a binary tree and postorderis the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

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

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

1 <= inorder.length <= 3000

postorder.length == inorder.length

-3000 <= inorder[i], postorder[i] <= 3000

inorder and postorderconsist of unique values.

Each value of postorderalso appears in inorder.

inorder is guaranteed to be the inorder traversal of the tree.

postorder is guaranteed to be the postorder traversal of the tree.

How to understand?

When every node value is unique, and the inorder and postorder traversal of the binary tree are given, create the binary tree from those.

Find the root from postorder traversal and use it in inorder traversal to get the left subtree and right subtree.

How to approach?

Recursion

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
    let idx_map = new Map<number, number>();
    let post_idx = postorder.length - 1;

    let helper = (in_left: number, in_right: number): TreeNode | null => {
        if (in_left > in_right) return null;
        let root_val = postorder[post_idx];
        let root = new TreeNode(root_val);
        let index = idx_map.get(root_val);
        post_idx--;
        root.right = helper(index + 1, in_right);
        root.left = helper(in_left, index - 1);
        return root;
    };
    
    for (let i = 0; i < inorder.length; i++) idx_map.set(inorder[i], i);
    return helper(0, inorder.length - 1);
}

set idx_map and post_idx

create helper function that takes left and right pointer for the inorder traversal.

create for loop to set the value and index in idx_map

return the helper function with input of 0 and the last index of inorder traversal.

in helper function when the left pointer is bigger than right pointer, return null.

create root_val as the postorder's post_idx value. For the first time, it will be the last value in the postorder array.

and create root with the root_val

index will be the value of root_val key in the idx_map.

and then decrement the post_idx by 1, this means from the end of the array it moves the pointer to the start of the array.

recursively call the helper function for the root.right and root.left with the index and input left pointer and input right pointer.

Right subtree will be built first and then there is no subtree for right node then it will backtrack to the point which can find the left subtree.

So index is the subtree's root index, it is the central pointer of the subtree to divide left subtree and right subtree.

lastly, in helper function return the root.