重建二叉树

根据前序遍历和中序遍历结果重建二叉树

思路：

1、前序遍历的第一个数字为原二叉树根节点的值；

2、遍历中序序列，找到根节点位置，根节点左边序列即为左子树所有节点，右边序列即为右子树所有节点；

3、用同样的方法（上面两个步骤）对剩下的小序列进行操作，即一个递归的过程。

具体代码

public class TreeNode {
    TreeNode left;
    TreeNode right;
    int value;
    public TreeNode(int value){
        this.value = value;
    }
    //pre：前序序列  in：中序序列
    public static TreeNode reBuild(int[]pre,int[]in){
        if(pre ==null ||in == null){
            return null;
        }
        TreeNode root = reBuildCore(pre,0,pre.length-1,in,0,in.length-1);
        return root;
    }

    private static TreeNode reBuildCore(int[]pre,int pStart,int pEnd,int[]in,int iStart,int iEnd) {
        if(pStart>pEnd || iStart > iEnd){
            return null;
        }
        TreeNode root = new TreeNode(pre[pStart]);
        for (int i = iStart; i <= iEnd; i++) {
            if(pre[pStart] == in[i]){
                //边界为前序遍历和中序遍历左子树序列边界
                root.left = reBuildCore(pre,pStart+1,pStart+(i-iStart),in,iStart,i-1);
                //边界为前序遍历和中序遍历右子树序列边界
                root.right = reBuildCore(pre,pStart+(i-iStart)+1,pEnd,in,i+1,iEnd);
            }

        }
        return root;
    }
    //前序遍历
    public static void prePrint(TreeNode head){
        if (head == null) {
            return;
        }
		System.out.print(head.value+" ");
        prePrint(head.left);
        prePrint(head.right);
        
    }
    public static void main(String[] args) {
        int preorder[] = {1, 2, 4, 7, 3, 5, 6, 8};
        int inorder[] = {4, 7, 2, 1, 5, 3, 8, 6};
        TreeNode treeNode = reBuild(preorder, inorder);
        System.out.println(treeNode.value);
        //prePrint(treeNode);

    }
}