根据前序遍历和中序遍历树构造二叉树.
你可以假设树中不存在相同数值的节点
给出中序遍历：[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);
}
```
