Reference: LeetCode 105, LeetCode 106 EPI 9.11
Difficulty: Medium

Problem

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:

Example:

1
2
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

Analysis

Methods:

  1. Recursion
    • Find Root: The node of preorder sequence from left to right is always the root of the current subtree.
    • Split Subtree Nodes: According to the root, we can split nodes in the inorder array into two parts belonging to left and right subtrees.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      public TreeNode buildTree(int[] preorder, int[] inorder) {
      if (preorder == null || inorder == null) {
      return null;
      }
      // preorder list
      LinkedList<Integer> preList = new LinkedList<>();
      for (int p : preorder) {
      preList.add(p);
      }
      return build(preList, inorder, 0, inorder.length - 1);
      }

      private TreeNode build(LinkedList<Integer> preList, int[] inorder, int lo, int hi) {
      if (lo > hi) {
      return null;
      // Don't write "if (lo == hi)", since you forget to do preList.removeFirst()
      }
      // get the root
      int rootVal = preList.removeFirst();
      TreeNode root = new TreeNode(rootVal);
      int rootIdx = getRootIdx(inorder, rootVal, lo, hi); // O(N)
      // left & right
      root.left = build(preList, inorder, lo, rootIdx - 1);
      root.right = build(preList, inorder, rootIdx + 1, hi);
      return root;
      }


      private int getRootIdx(int[] inorder, int rootVal, int lo, int hi) {
      for (int i = lo; i <= hi; ++i) {
      if (inorder[i] == rootVal) {
      return i;
      }
      }
      return -1;
      }

Time: $O(N\log{N})$ in the best case, and $O(N^2)$ in the worst case, since at each level it takes $O(N)$ to find the root index.
Space: $O(h)$

  1. Recursion (HashMap)
    • Use a HashMap to map the values to indices.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      public TreeNode buildTree(int[] preorder, int[] inorder) {
      if (preorder == null || inorder == null) {
      return null;
      }
      // preorder list
      LinkedList<Integer> preList = new LinkedList<>();
      for (int p : preorder) {
      preList.add(p);
      }
      // inoder mapping (val -> index)
      Map<Integer, Integer> map = new HashMap<>();
      for (int i = 0; i < inorder.length; ++i) {
      map.put(inorder[i], i);
      }
      return build(preList, inorder, 0, inorder.length - 1, map);
      }

      private TreeNode build(LinkedList<Integer> preList, int[] inorder, int lo, int hi, Map<Integer, Integer> map) {
      if (lo > hi) {
      return null;
      }
      // get the root
      int rootVal = preList.removeFirst();
      TreeNode root = new TreeNode(rootVal);
      int rootIdx = map.get(rootVal); // O(1)
      // left & right
      root.left = build(preList, inorder, lo, rootIdx - 1, map);
      root.right = build(preList, inorder, rootIdx + 1, hi, map);
      return root;
      }

Time: $O(N)$
Space: $O(N)$

Here is the version of Postorder + Inorder:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (postorder == null || inorder == null) {
return null;
}
// postorder list
LinkedList<Integer> postList = new LinkedList<>();
for (int p : postorder) {
postList.add(p);
}
// inoder mapping (val -> index)
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; ++i) {
map.put(inorder[i], i);
}
return build(postList, inorder, 0, inorder.length - 1, map);
}

private TreeNode build(LinkedList<Integer> postList, int[] inorder, int lo, int hi, Map<Integer, Integer> map) {
if (lo > hi) {
return null;
}
// get the root
int rootVal = postList.removeLast();
TreeNode root = new TreeNode(rootVal);
int rootIdx = map.get(rootVal); // O(1)
// right & left
root.right = build(postList, inorder, rootIdx + 1, hi, map);
root.left = build(postList, inorder, lo, rootIdx - 1, map);
return root;
}

Comment