重建二叉树算法总结

输入二叉树的前序遍历序列和中序遍历序列，重建二叉树。

下面代码假设输入序列是：前序遍历序列和中序遍历序列

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return reBuild(pre, in, 0, pre.length-1, 0, in.length-1);
    }
    /**
     * reBuid函数参数的定义很重要！！！节点在前序遍历序列和后序遍历序列中的开始和结束位置，一定要分开定义
     * 不然在算法中会产生歧义。
     *
     */
    public TreeNode reBuild(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart >= preEnd) {
            if (preStart == preEnd) {
                return new TreeNode(pre[preStart]);
            }
            return null;
        }
        int inRoot = find(inStart, inEnd, pre[preStart], in);
        int lengthOfLeft = inRoot - inStart;
        TreeNode root = new TreeNode(pre[preStart]);
        root.left = reBuild(pre, in, preStart+1, preStart+lengthOfLeft, inRoot-lengthOfLeft, inRoot-1);
        root.right = reBuild(pre, in, preStart+lengthOfLeft+1, preEnd, inRoot+1, inEnd);
        return root;
    }
    public int find(int start, int end, int val, int[] in) {
        for (int i = start; i <= end; i++) {
            if (val == in[i]) {
                return i;
            }
        }
        return -1;
    }
}