Construct Binary Tree from Inorder and Postorder Traversal

Leetcode Problem 106: Construct Binary Tree from Inorder and Postorder Traversal

Problem Summary

Given two integer arrays inorder and postorder representing the in-order and post-order traversals of the same binary tree (all values unique), construct and return the binary tree.

Constraints:

• The tree has between 1 and 3,000 nodes.
• All node values in each array are unique and in the range [-3,000, 3,000].
• postorder and inorder contain the same set of values.

Techniques

• Array
• Hash Table
• Divide and Conquer
• Tree
• Binary Tree

Solution

export 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 buildTreeWith(
    inorder: number[],
    postorder: number[],
    inorderRootIndexes: Map<number, number>
): TreeNode | null {
    if (inorder.length === 0 || postorder.length === 0) {
        return null
    }

    const root = postorder[postorder.length - 1]
    const rootIndex = inorderRootIndexes.get(root)!

    return new TreeNode(
        root,
        buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex)),
        buildTree(inorder.slice(rootIndex + 1, inorder.length), postorder.slice(rootIndex, postorder.length - 1))
    )
}

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
    const inorderIndexes = new Map<number, number>()

    for (let i = 0; i < inorder.length; i++) {
        inorderIndexes.set(inorder[i], i)
    }

    return buildTreeWith(inorder, postorder, inorderIndexes)
}