LeetCode Top Interview 150

105. Construct Binary Tree from Preorder and Inorder Traversal

Medium

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is 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 inorder consist of unique values.
• Each value of inorder also 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.

Solution

import { TreeNode } from '../../com_github_leetcode/treenode'

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    let preorderIdx = 0
    const inorderValIdxMap: Map<number, number> = new Map()
    for (let i = 0; i < inorder.length; i++) {
        inorderValIdxMap.set(inorder[i], i)
    }
    const constuctTreePreorder = (left: number, right: number): TreeNode | null => {
        if (left > right) {
            return null
        }
        const root = new TreeNode(preorder[preorderIdx++])
        const inorderRootIdx = inorderValIdxMap.get(root.val)
        root.left = constuctTreePreorder(left, inorderRootIdx - 1)
        root.right = constuctTreePreorder(inorderRootIdx + 1, right)
        return root
    }
    return constuctTreePreorder(0, preorder.length - 1)
}

export { buildTree }

This site is open source. Improve this page.