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         // bug 3: consider when length is 0.
13         if (preorder == null || inorder == null || preorder.length == 0 || preorder.length != inorder.length) {
14             return null;
15         }
16         
17         // bug 4: end index is length - 1.
18         return buildTree(preorder, inorder, 0, preorder.length - 1, 0, preorder.length - 1);
19     }
20     
21     public TreeNode buildTree(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
22         // base case;
23         if (preStart > preEnd) {
24             return null;
25         }
26         
27         int rootVal = preorder[preStart];
28         TreeNode root = new TreeNode(rootVal);
29         
30         int pos = findTarget(inorder, rootVal, inStart, inEnd);
31         
32         // bug 5: left number is pos - instart can‘t add 1
33         int leftNum = pos - inStart;
34         
35         root.left = buildTree(preorder, inorder, preStart + 1, preStart + leftNum, inStart, pos - 1);
36         root.right = buildTree(preorder, inorder, preStart + leftNum + 1, preEnd, pos + 1, inEnd);
37         
38         return root;
39     }
40     
41     // bug 1: return type required.
42     // bug 2: this is not a bst. can‘t use binary search.
43     public int findTarget(int[] A, int target, int start, int end) {
44         for (int i = start; i <= end; i++) {
45             if (target == A[i]) {
46                 return i;
47             }
48         }
49         
50         return -1;
51     }
52 }