105. Construct Binary Tree from Preorder and Inorder Traversal

Problem:

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

Analysis:

This problem takes me a while to understand the solution. Consider the binary tree below:

preorder sequence is: 4,2,1,3,6,5,7
inorder sequence is: 1,2,3,4,5,6,7

We can find the root easily with preorder array. The root is 4 in preorder array, the left and right trees are [1,2,3] and [5,6,7] respectively.  Then construct the sub trees recursively.

The root.left's root is easy to determine, it is located at preStart + 1. The right subtree's root is number of nodes in left subtree away from parent root. That is preStart + inIndex - inStart + 1.

Use a hashmap to catch index of inorder array reduces time complexity to O(n).

Solution:

 /**  
  * Definition for a binary tree node.  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 class Solution {  
   public TreeNode buildTree(int[] preorder, int[] inorder) {  
     Map<Integer, Integer> inMap = new HashMap<>();  
           for (int i = 0; i < inorder.length; i++) {  
                inMap.put(inorder[i], i);  
           }  
     return helper(0, 0, inorder.length - 1, preorder, inMap);  
   }  
      private TreeNode helper(int preStart,   
               int inStart,   
               int inEnd,   
               int[] preorder,   
               Map<Integer, Integer> inMap) {  
           if (inStart > inEnd ) return null;  
           TreeNode root = new TreeNode(preorder[preStart]);  
           int inIndex = inMap.get(root.val);  
           root.left = helper(preStart + 1,   
               inStart,   
               inIndex - 1,   
               preorder,   
               inMap);  
           root.right = helper(preStart + inIndex - inStart + 1,   
               inIndex + 1,   
               inEnd,   
               preorder, i  
               nMap);  
           return root;  
      }  
 }