105. Construct Binary Tree from Preorder and Inorder Traversal Leetcode Java

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

Note:
You may assume that duplicates do not exist in the tree.

Solution:

Several information we can conclude from preorder and inorder array

1. The first element in preorder array must be the root node. 

2. All the left nodes from root node in inorder array must be root's left children.

3. All the right nodes from root node in inorder array must be root's right children.

4. All root's left children must be in front of its right children in preorder array.

So the pattern of these two arrays looks like:

preorder: [root]+{left children}+ {right children}

inorder: {left children}+[root]+ {right children}

For left children and right children, they are subtrees of the root, and they are also trees, so we can recursively construct the tree base on the information we have.

The algorithm is based on our observation and include following steps:

1. Find the position of the root in inorder array

2. Divide the preorder and inorder array to 3 parts: left subtree, root, right subtree

3. Construct the left subtree, right subtree using the same technique

4. Recursively construct the tree from leaf to root.
Here I search the array every time when I try to divide the array. In next problem construct binary tree from postorder and inorder tranversal I use an extra hashmap to map the index and the value of Inorder array, which can definitely improve the time performance.

 public TreeNode buildTree(int[] preorder, int[] inorder) {  
     if(preorder==null || inorder==null ||preorder.length!=inorder.length) return null;  
     return helper(0,0,preorder.length-1,preorder,inorder);  
   }  
   public TreeNode helper(int start1, int start2, int l, int[] preorder, int[] inorder){  
     if(start1<0 || start2<0 || start1 >= preorder.length || start2>=inorder.length || l<0) return null;  
     TreeNode root=new TreeNode(preorder[start1]);  
     for(int i=start2;i<=start2+l;i++){  
       if(inorder[i]==preorder[start1]){  
         TreeNode leftNode=helper(start1+1,start2,i-1-start2,preorder,inorder);  
         TreeNode rightNode=helper(start1+i-start2+1,i+1,start2+l-i-1,preorder,inorder);  
         root.left=leftNode;  
         root.right=rightNode;  
         return root;  
       }  
     }  
     return null;  
   }