剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点

解题思路：

前序遍历：[根节点|左子树|右子树]

中序遍历：[左子树|根节点|右子树]

分治算法解析：

• 递推参数： 根节点在前序遍历的索引 root 、子树在中序遍历的左边界 left 、子树在中序遍历的右边界 right ；

• 终止条件： 当 left > right ，代表已经越过叶节点，此时返回 n u l l null null ；

• 递推工作：

  1. 建立根节点root： 节点值为 preorder[root] ；

  2. 划分左右子树： 查找根节点在中序遍历 inorder 中的索引 index ；

  3. 构建左右子树： 开启左右子树递归

     	根节点索引	中序遍历左边界	中序遍历右边界
     左子树	root+1	left	index-1
     右子树	root+index-left+1	index+1	rigth

     TIPS：root+index-left+1的含义为根节点索引+左子树长度+1

• 返回值： 回溯返回root，作为上一层递归中根节点的左/右子节点；

class Solution {
    //利用原理,前序遍历的第一个节点就是根，在中序遍历中通过根区分哪些是左子树的，哪些是右子树的
    //左右子树，递归
    Map map = new HashMap<>();//标记中序遍历
    int[] preorder;//保留的前序遍历

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return recur(0, 0, inorder.length-1);
    }

    
    public TreeNode recur(int pre_root, int in_left, int in_right) {
        //相等就是自己
        if (in_left > in_right) {
            return null;
        }
        //pre_root是在前序遍历里面的
        TreeNode root = new TreeNode(preorder[pre_root]);
        // 有了前序的，再根据前序的，在中序中获当前根的索引
        int index = map.get(preorder[pre_root]);

        //左子树的根节点就是左子树的（前序遍历）第一个，就是pre_root+1, 左边边界就是left，右边边界是中间区分的index - 1
        root.left = recur(pre_root + 1, in_left, index - 1);

        //左子树的长度 = index - 1 - in_left + 1
        //右子树的根节点就是右子树的（前序遍历）第一个, 就是当前根节点加上左子树的长度+1，即pre_root + (index - 1 - in_left + 1)  + 1
        root.right = recur(pre_root + (index - 1 - in_left + 1)  + 1, index + 1, in_right);

        //最后返回根节点
        return root;
    }
}

输入某二叉树的后续遍历和中序遍历的结果，请构建该二叉树并返回其根节点

class Solution {
    Map map = new HashMap();
    int[] postorder;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;

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

        return recur(postorder.length - 1, 0, inorder.length - 1);
    }

    
    public TreeNode recur(int post_root, int in_left, int in_right){
        if (in_left > in_right) {
            return null;
        }
        //获取根节点在中序遍历中对应的索引
        int index = map.get(postorder[post_root]);
        //获取节点
        TreeNode root = new TreeNode(postorder[post_root]);

        root.left = recur(post_root - (in_right - index + 1), in_left, index - 1);
        root.right = recur(post_root - 1, index + 1, in_right);

        return root;
    }
}