根據前序遍歷和中序遍歷樹構造二叉樹.
你可以假設樹中不存在相同數值的節點
給出中序遍歷：[1,2,3]和前序遍歷：[2,1,3]. 返回如下的樹:
```
2
/ \
1 3
```
**規則**
輸入：兩個數組 int a[] 和 int b[]
輸出：頭結點Head
case：
```
數組為null或length為0
兩個數組長度不一致，內容不同
只有一個元素
只有兩個元素
都在左側
都在右側
兩邊都有
```
**思路**
對一個實例`{1,2,4,7,3,5,6,8},{4,7,2,1,5,3,8,6}`進行分析后，可以得出這樣的規則
```
a[0]為頭節點，在b中找到該節點位置3，那么a從1開始，共3個元素為左邊子樹，4-end為右邊子樹
設每次數組有范圍ae~ab be-bb bi為a[ae]也就是節點在b數組中的index
左 ab = ab+1 ae =ab+1+size bb = bb be = bi - 1 size = bi-1-bb
右 ab = ab+1+size+1 ae=ae bb=bi+1 be=be
其中，ae不能大于ab be不能大于bb 否則返回null
```
**代碼**
```
public class Solution {
/**
*@param preorder : A list of integers that preorder traversal of a tree
*@param inorder : A list of integers that inorder traversal of a tree
*@return : Root of a tree
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || inorder == null) {return null;}
if(preorder.length * inorder.length == 0) {return null;}
if(preorder.length != inorder.length) {return null;}
return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
private TreeNode buildTree (int[] a,int ab,int ae, int[] b,int bb,int be) {
if(ab > ae || bb > be) {
return null;
}
TreeNode node = new TreeNode(a[ab]);
int bi = -1;
for(int i = bb ;i <= be ; i++) {
if(b[i] == a[ab]) {
bi = i;
break;
}
}
if(bi == -1) {
throw new NullPointerException("cannot find "+a[ab]);
}
node.left = buildTree(a,ab+1,(ab+1)+(bi-1-bb),b,bb,bi-1);
node.right = buildTree(a,(ab+1)+(bi-1-bb)+1,ae,b,bi+1,be);
return node;
}
}
```
**測試代碼**
```
public class TreeNode {
public int val;
public TreeNode left, right;
public TreeNode(int val) {
this.val = val;
this.left = this.right = null;
}
public static String print(TreeNode node) {
Deque<TreeNode> queue = new LinkedList<TreeNode>();
if(node == null) {
return "-1,";
}
queue.addLast(node);
StringBuilder sb = new StringBuilder();
while(!queue.isEmpty()) {
TreeNode thisNode = queue.removeFirst();
if(thisNode == null) {
sb.append("-1,");
}else {
sb.append(thisNode.val+",");
queue.addLast(thisNode.left);
queue.addLast(thisNode.right );
}
}
return sb.toString();
}
public static TreeNode build(String tree) {
String arr [] = tree.split(",");
TreeNode allNode [] = new TreeNode[arr.length];
for(int i = 0; i < arr.length; i++) {
int val = Integer.parseInt(arr[i]);
if(val == -1) {
allNode[i] = null;
}else {
allNode[i] = new TreeNode(val);
}
}
for(int i = 0; i < arr.length; i++) {
TreeNode node = allNode[i];
int li = i*2 + 1;
int ri = i*2 + 2;
if(node != null) {
node.left = (li > allNode.length-1) ? null : allNode[li];
node.right = (ri > allNode.length-1)? null : allNode[ri];
}
}
return allNode[0];
}
public static void main(String[] args) {
TreeNode head = build("1,2,3,-1,4");
System.out.println(TreeNode.print(head));
}
}
```
```
public void test1()
{
int t1 [][]= new int[][]{{2,1,3},{1,2,3}};
RebuildTree1 builder = new RebuildTree1();
TreeNode head = builder.buildTree(t1[0], t1[1]);
assertResult(head,"2,1,3");
int t2 [][]= new int[][]{{1,2,4,7,3,5,6,8},{4,7,2,1,5,3,8,6}};
head = builder.buildTree(t2[0], t2[1]);
assertResult(head,"1,2,3,4,-1,5,6,-1,7,-1,-1,8,-1");
}
private void assertResult(TreeNode head,String rs) {
System.out.println(TreeNode.print(head));
assertTrue(TreeNode.print(head).indexOf(rs) == 0);
}
```
