106. Construct Binary Tree from Inorder and Postorder Traversal

Array Hash Table Tree Binary Tree Divide and Conquer

Time: O(n)

Space: O(n)

Intuition

The last element of postorder is always the root. Find it in inorder to split into left and right subtrees. The number of elements in the left inorder slice tells you exactly how many elements belong to the left postorder slice.

Algorithm

1Build a map: inorder value -> index.
2Recurse with (inLeft, inRight, postRight).
3Root = postorder[postRight]. Find its inorder index rootIdx.
4Left subtree size = rootIdx - inLeft.
5Recurse left: (inLeft, rootIdx-1, postRight-1-(inRight-rootIdx)).
6Recurse right: (rootIdx+1, inRight, postRight-1).

Example Walkthrough

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

1.Root=3 (postorder last). rootIdx=1 in inorder.
2.Left: inorder[0..0]=[9], postorder[0..0]=[9] -> root=9.
3.Right: inorder[2..4]=[15,20,7], postorder[1..3]=[15,7,20] -> root=20, etc.

Output: Tree [3,9,20,null,null,15,7]

Common Pitfalls

•Use a HashMap for inorder lookups - linear search makes this O(n^2).

106.cs

// Approach: HashMap stores inorder indices for O(1) lookup. The last element
// of postorder is always the root; recurse on left and right subarrays.
// Time: O(n) Space: O(n)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public TreeNode BuildTree(int[] inorder, int[] postorder)
    {
        Dictionary<int, int> inToIndex = new Dictionary<int, int>();

        for (int i = 0; i < inorder.Length; ++i)
            inToIndex[inorder[i]] = i;

        return Build(inorder, 0, inorder.Length - 1, postorder, 0, postorder.Length - 1, inToIndex);
    }

    private TreeNode Build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd,
                           Dictionary<int, int> inToIndex)
    {
        if (inStart > inEnd)
            return null;

        int rootVal = postorder[postEnd];
        int rootInIndex = inToIndex[rootVal];
        int leftSize = rootInIndex - inStart;

        TreeNode root = new TreeNode(rootVal);
        root.left = Build(inorder, inStart, rootInIndex - 1, postorder, postStart,
                          postStart + leftSize - 1, inToIndex);
        root.right = Build(inorder, rootInIndex + 1, inEnd, postorder, postStart + leftSize,
                           postEnd - 1, inToIndex);
        return root;
    }
}

Was this solution helpful?