Construct Binary Tree from Inorder and Postorder Traversal

LeetCode 106 | Difficulty: Medium

Medium

Problem Description

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is 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 `postorder` consist of **unique** values.

- Each value of `postorder` also 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.

Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 124 ms)

Metric	Value
Runtime	124 ms
Memory	N/A
Date	2018-05-20

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode BuildTree(int[] inorder, int[] postorder) {
        return BuildTreeIP(inorder, 0, inorder.Length-1, postorder, 0, postorder.Length-1);
}

public TreeNode BuildTreeIP(int[] inorder,int ins, int ie, int[] postorder, int ps, int pe)
{
    if(ins>ie || ps>pe) return null;
    TreeNode root = new TreeNode(postorder[pe]);
    int index = Array.IndexOf(inorder, postorder[pe]);
    root.left = BuildTreeIP(inorder, ins, index - 1, postorder, ps, ps + index - ins - 1);
    root.right = BuildTreeIP(inorder, index+1, ie, postorder, ps + index - ins, pe-1);
    return root;
}
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.
• Hash map gives O(1) lookup — think about what to use as key vs value.