剑指Offer 07.重建二叉树

首先应该明确：（前序遍历+中序遍历）和（后序遍历+中序遍历）能唯一确定一棵二叉树；而前序遍历[根节点左子树右子树]和后序遍历[左子树右子树根节点]不能唯一确定一颗二叉树。

因为我们不能从这两种遍历中区分出左子树和右子树的区间。这里有一个例子

但是如果这棵树是真二叉树（所有节点的度要么为0，要么为2，即左儿子和右儿子同时存在），那么（前序遍历+后序遍历）就能重构一棵二叉树。如下图所示：

分析一下：二叉树前序遍历的第一个元素和后序遍历的最后一个元素为树根，后序遍历序列的倒数第二个元素为右子树的根，前序遍历中右子树的根的前面的元素均为左子树元素，从而分隔左右子树的元素，因此可以采用递归依次构建每一棵子树。

前序[1,2,4,5,3,6,7]

后序[4,5,2,6,7,3,1]

对于前序遍历，1后面的2是左子树的根节点；对于右子树，1前面的3是右子树的根节点。左子树的根节点2，在后序遍历中2之前的（包括2，都是左子树的部分）。

下面给出重构一棵二叉树的各种形式：

1、前序+中序

public HashMap<Integer, Integer> map;   //建立<节点值，数组下标>的映射关系

    /* 重构一棵二叉树：前序遍历 + 中序遍历
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();

        int len = preorder.length;

        for (int i = 0; i < len; i++) {
            map.put(inorder[i], i);
        }

        return myBuildTree(preorder, inorder, 0, len-1, 0, len-1);
    }

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preOrderLeft, int preOrderRight, int inOrderLeft, int inOrderRight) {
        //先判断一下是否合法
        if (preOrderLeft > preOrderRight) {
            return null;
        }

        //确定根节点
        int preOrderRoot = preOrderLeft;
        TreeNode root = new TreeNode(preorder[preOrderRoot]);

        int inOrderRoot = map.get(root.val);
        int sizeOfLeftTree = inOrderRoot - inOrderLeft; //  左子树的大小

        //构建左子树
        root.left = myBuildTree(preorder, inorder, preOrderLeft+1, preOrderLeft+sizeOfLeftTree, inOrderLeft,inOrderRoot-1);

        //构建右子树
        root.right = myBuildTree(preorder, inorder, preOrderLeft+sizeOfLeftTree+1, preOrderRight, inOrderRoot+1,inOrderRight);

        return root;
    }

2、中序+后序

public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        int len = inorder.length;

        for (int i = 0; i < len; i++) {
            map.put(inorder[i], i);
        }
        return myBuildTree(inorder, postorder, 0, len-1, 0, len-1);
    }

    public TreeNode myBuildTree(int[] inorder, int[] postorder, int inOrderLeft, int inOrderRight, int postOrderLeft, int postOrderRight) {
        //合法性判断
        if (inOrderLeft > inOrderRight || postOrderLeft > postOrderRight) {
            return null;
        }

        //根节点
        int postOrderRoot = postOrderRight;
        TreeNode root = new TreeNode(postorder[postOrderRoot]);
        int inOrderRoot = map.get(root.val);
        int sizeOfLeftTree = inOrderRoot - inOrderLeft;

        //建立左子树
        root.left = myBuildTree(inorder, postorder, inOrderLeft, inOrderRoot-1, postOrderLeft, postOrderLeft + sizeOfLeftTree-1);

        //建立右子树
        root.right = myBuildTree(inorder, postorder, inOrderRoot+1, inOrderRight, postOrderLeft+sizeOfLeftTree+1, postOrderRoot-1);

        return root;
    }

3、前序+后序

private HashMap<Integer, Integer> map; //<值，下标>
    public TreeNode buildTree(int[] preorder, int[] postorder) {
        if (preorder.length != postorder.length) {
            return null;
        }

        map = new HashMap<>();

        int len = preorder.length;

        for (int i = 0; i < len; i++) {
            map.put(postorder[i], i);
        }

        return myBuildTree(preorder, postorder, 0, len-1, 0, len-1);
    }

    public TreeNode myBuildTree(int[] preorder, int[] postorder, int preOrderLeft, int preOrderRight, int postOrderLeft, int postOrderRight) {
        //合理性判断
        if (preOrderLeft > preOrderRight || postOrderLeft > postOrderRight) {
            return null;
        }

        //注意这个特判条件，否则4会出现数组越界
        if (preOrderLeft == preOrderRight || postOrderLeft == postOrderRight) {
            TreeNode res = new TreeNode(preorder[preOrderLeft]);
            return res;
        }

        //根节点
        int preOrderRoot = preOrderLeft;
        TreeNode root = new TreeNode(preorder[preOrderLeft]);

        //前序遍历的第二个节点就是左子树的根节点
        int preOrderLeftTreeRoot = preOrderLeft + 1; //3
        int postOrderLeftTreeRoot = map.get(preorder[preOrderLeftTreeRoot]);    //4

        //确定左子树的长度
        int sizeOfLeftTree = postOrderLeftTreeRoot - postOrderLeft + 1;

        //确定右子树的长度
        int sizeOfRightTree = postOrderRight - postOrderLeftTreeRoot - 1;

        //构建左子树
        root.left = myBuildTree(preorder, postorder, preOrderLeftTreeRoot, preOrderLeftTreeRoot+sizeOfLeftTree-1, postOrderLeft, postOrderLeftTreeRoot);

        //构建右子树
        root.right = myBuildTree(preorder, postorder, preOrderLeftTreeRoot+sizeOfLeftTree, preOrderRight, postOrderLeftTreeRoot+1, postOrderLeftTreeRoot+sizeOfRightTree);

        return root;
    }

剑指Offer 07.重建二叉树

推荐阅读