[Leetcode] 105. Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorderand inorderwhere preorderis the preorder traversal of a binary tree and inorderis the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

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

Example 2:

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

Constraints:

1 <= preorder.length <= 3000

inorder.length == preorder.length

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

preorder and inorderconsist of unique values.

Each value of inorderalso appears in preorder.

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

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

How to understand?

Use the given preorder and inorder traversal to build the binary tree.

Preorder will give the root of the binary tree and inorder will give the left subtree and right subtree from the given root.

How to approach?

Recursion

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    let idx_map = new Map<number, number>()
    let pre_idx = 0

    function helper(left: number, right: number) {
        if (left > right) return null;
        let root_val = preorder[pre_idx]
        let root = new TreeNode(root_val)
        let index = idx_map.get(root_val)

        pre_idx++
        root.left = helper(left, index - 1)
        root.right = helper(index + 1, right)

        return root
    }

    for (let i = 0; i < inorder.length; i++) idx_map.set(inorder[i], i)
    return helper(0, inorder.length - 1)
};

create the map for inorder traversal and initialize the preordre index as 0

create for loop to set the inorder value to inorder index key.

return the helper function with the range of 0 to last index of inorder.

helper function takes left and right pointer to check the range of them in inorder map.

when the left pointer is bigger than right node return null.

create root_val from preorder with the pre_idx. firstly it will be the root of the entire binary tree.

create the tree node root from root_val.

and get the index from inorder map use root_val.

increment pre_idx by 1. it moves pointer to the right in the preorder traversal.

since preorder traversal's order is root > left > right, so call the helper function for root.left first and then call the helper function for root.right.

use the left pointer, index, and right pointer.

lastly return the root.