前序遍历和中序遍历树构造二叉树

   2
 /  \
1    3

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = 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.length == 0 || inorder.length == 0) {
			return null;
		}

		int root = preorder[0]; // 根据前序遍历的规律取第一个最为根节点
		TreeNode treeRoot = new TreeNode(root);

		int flag = -1;			// flag用于存放根节点root在中序遍历中的位置
		for (int i = 0; i < inorder.length; i++) {
			if (inorder[i] == root) {
				flag = i;
			}
		}
		
		//前序或中序遍历等于1，则说明已经是叶子节点，直接return即可，避免多余运算
		if (preorder.length == 1 || inorder.length == 1) {
			return treeRoot;
		}
		
		int[] child_InorderLeft = new int[flag];    					  //左侧子节点的中序遍历
		int[] child_InorderRight = new int[(inorder.length - 1) - flag];  //右侧子节点的中序遍历
		int[] child_PreorderLeft = new int[flag];						  //左侧子节点的前序遍历
		int[] child_PreorderRight = new int[child_InorderRight.length];	  //右侧子节点的前序遍历
		
		
		//从现有的中序遍历中拿到 左右子节点的中序遍历
		for (int i = 0; i < inorder.length; i++) {
			if (i < flag) {
				child_InorderLeft[i] = inorder[i];
			}
			else if ((i > flag) ){
				child_InorderRight[i - flag - 1] = inorder[i];
			}
		}
		
		//从现有的前序遍历中拿到 左右子节点的前序遍历
		for (int i = 1; i < preorder.length ; i++) {  //这里i从1开始，是因为i的preorder[0]为根节点
			if(i <= flag)
				child_PreorderLeft[i-1] = preorder[i];   //preorderSeed[i-1] 是因为要新左子树要从0存放，不然preorderSeed[0]就是空的，而且长度会不够
			else { 
				child_PreorderRight[i - flag - 1] = preorder[i];
			}
		}
		
		//递归调用获取左右子树
		treeRoot.left = buildTree(child_PreorderLeft,child_InorderLeft);
		treeRoot.right = buildTree(child_PreorderRight,child_InorderRight);
		
		return treeRoot;
	}
}