105. Construct Binary Tree from Preorder / Postorder and Inorder Traversal

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:

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

Return the following binary tree:

  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.

     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)$

2. Recursion (HashMap)

   • Use a HashMap to map the values to indices.

     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:

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;
}