[Leetcode]-- Construct Binary Tree from Preorder and Inorder Traversal

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public  TreeNode buildTree(int[] preorder, int[] inorder) {
12         if (preorder == null || inorder == null) {
13             return null;
14         }
15         int preLen = preorder.length;
16         int inLen = inorder.length;
17         if (preLen == 0 || inLen == 0) {
18             return null;
19         }
20 
21         return constructTree(preorder, 0, preLen - 1, inorder, 0, inLen - 1);
22     }
23 
24     public static TreeNode constructTree(int[] preorder, int preStart, int preEnd,
25             int[] inorder, int inStart, int inEnd) {
26         int rootValue = preorder[preStart];
27         TreeNode root = new TreeNode(rootValue);
28         root.left = null;
29         root.right = null;
30         if (preStart == preEnd && preorder[preStart] == inorder[inStart]) {
31             return root;
32         }
33 
34         int i = inStart;
35         for (; i <= inEnd; i++) {
36             if (rootValue == inorder[i]) {
37                 break;
38             }
39         }
40         int leftLen = i - inStart;
41         // exsit left subtree
42         if (leftLen > 0) {
43             root.left = constructTree(preorder, preStart + 1, preStart
44                     + leftLen, inorder, inStart, i - 1);
45         }
46         if (inEnd > i) {
47             root.right = constructTree(preorder, preStart + leftLen + 1,
48                     preEnd, inorder, i + 1, inEnd);
49         }
50         return root;
51     }
52 
53 }

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public TreeNode buildTree(int[] preorder, int[] inorder) {
12         return  build(preorder, inorder,  0, preorder.length-1, 0, preorder.length);
13     }
14     
15     private TreeNode build(int[] preorder, int[] inorder, int pStart, int pEnd, int iStart, int iEnd){
16         
17         if(pStart > pEnd) return null;
18         
19         int rootVal =  preorder[pStart];
20         int i = iStart;
21         for( ; i<iEnd; i++){
22             if(inorder[i] == rootVal)
23                 break;
24         }
25         
26         TreeNode node = new TreeNode(rootVal);
27         node.left = build(preorder, inorder, pStart+1, i-iStart+pStart, iStart, i-1);
28         node.right = build(preorder, inorder, i-iStart+pStart+1, pEnd, i+1, iEnd);
29         return node;
30     }
31 }