根据前序遍历和中序遍历树构造二叉树.

你可以假设树中不存在相同数值的节点

给出中序遍历：[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);
    }