剑指Offer 面试题06：重建二叉树

/**
 * 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 == null || pre.length == 0 || in == null || in.length ==0) {
            return null;
        }
        
        // 在前序遍历序列中找到根节点的值，并重建根节点
        int headValue = pre[0];
        TreeNode headTreeNode = new TreeNode(headValue);
        
        // 遍历中序序列，得到左子树节点数与右节点节点数
        int leftSubTreeCount = 0;
        int rightSubTreeCount = 0;
        boolean isLeft = true;
        for (int i = 0; i < in.length; i++) {
            int currentValue = in[i];
            if (currentValue == headValue) {
                isLeft = false;
                continue;
            } else if(isLeft){
                leftSubTreeCount++;
            } else if(!isLeft) {
                rightSubTreeCount++;
            }
        }
        
        // 获得左右子树的前序以及中序遍历序列
        int leftPreOffset = 1;
        int leftInOffset = 0;
        int[] leftPre = this.copyArray(pre, leftPreOffset, leftSubTreeCount);
        int[] leftIn = this.copyArray(in, leftInOffset, leftSubTreeCount);
        
        int rightPreOffset = 1 + leftSubTreeCount;
        int rightInOffset = rightPreOffset;
        int[] rightPre = this.copyArray(pre, rightPreOffset, rightSubTreeCount);
        int[] rightIn = this.copyArray(in, rightInOffset, rightSubTreeCount);
        
        // 递归调用，重建左右子树
        TreeNode leftSubTreeNode = reConstructBinaryTree(leftPre, leftIn);
        TreeNode rightSubTreeNode = reConstructBinaryTree(rightPre, rightIn);
        
        // 根节点关联左右子树
        headTreeNode.left = leftSubTreeNode;
        headTreeNode.right = rightSubTreeNode;
        return headTreeNode;
    }
    
    private int[] copyArray(int[] sourceArray, int offset, int count) {
        int[] resultArray = new int[count];
        for(int i = 0; i < count; i++) {
            resultArray[i] = sourceArray[offset];
            offset++;
        }
        return resultArray;
    }
}