剑指offer刷题第四题

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length == 0)
			return null;
		int val = pre[0];
		TreeNode root = new TreeNode(val);
		int rootPositionInOrder = 0;
		for(int i = 0;i < in.length;i++)
			if(in[i] == val) {
				rootPositionInOrder = i;
				break;
			}
		int[] leftPre = new int[rootPositionInOrder];
		int[] leftIn = new int[rootPositionInOrder];
		int[] rightPre = new int[in.length - 1 - rootPositionInOrder];
		int[] rightIn = new int[in.length - 1 - rootPositionInOrder];
		System.arraycopy(pre, 1, leftPre, 0, leftPre.length);
		System.arraycopy(pre, leftPre.length + 1, rightPre, 0, rightPre.length);
		System.arraycopy(in, 0, leftIn, 0, leftIn.length);
		System.arraycopy(in, rootPositionInOrder + 1, rightIn, 0, rightIn.length);
		root.left = reConstructBinaryTree(leftPre, leftIn);
		root.right = reConstructBinaryTree(rightPre,rightIn);
		return root;
    }
}