题解 | #重建二叉树#递归来解已拿捏

默认你已经理解题意

这道题既然要重建二叉树，那重建一颗二叉树需要啥？

• 根节点
• 左节点
• 右节点

如何找到第一个根节点呢？

那为啥是第一个根节点呢？

因为你从第一个根节点开始创建的呀，不是吗

前序遍历： 根节点 -- 左节点 -- 右节点
中序遍历： 左节点 -- 根节点 -- 右节点

根据上面的性质，我们晓得了第一个根节点必然出现在前序遍历的第一个位置！

但是对中序遍历来说，我们不知道第一个根前面的左子树长度，所以无法得知！因此最简单的切入点就是通过前序遍历找到第一个根节点，是最简单的了

第二个问题，如何找到第一个左节点？

这个在前序遍历很好看出来，第一个左节点就在第一个根节点的右边+1个单位，即：pre_root_index + 1

最后如何找到第一个右节点？

对前序遍历来说，我们已经知道了根、左节点，那么很显然，右节点的下标 = 根节点下标 + 左子树的长度 + 1（在前序遍历数组中），但是现在唯一不确定的就是左子树的长度，这一点可以很简单的从中序遍历得出来，也就是左子树长度 = 根节点下标 - 左子树的左边界 （这个是在中序遍历数组的时候）

准备工作已经做完了，开始重建

那怎么得到一个完整的二叉树，肯定是递归调用啦，那么请你注意三个要素就可以了：

• 1 出口条件在哪儿
• 2 递归要操作是啥
• 3 如何得到返回值

class Solution {
    int[] preorder;
    HashMap<Integer, Integer> map = new HashMap<>();
    // 前序遍历 preorder: 根 -- 左 -- 右   第一个肯定是根节点
    // 中序遍历 inorder: 左 -- 根 -- 右
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return rebuild(0, 0, inorder.length - 1);  
    }

    // pre_root_index : 根节点 在 前序遍历中的下标
    // in_left_index: 该节点在中序遍历中的左边界
    // in_right_index: 该节点在中序遍历中的右边界
    public TreeNode rebuild(int pre_root_index, int in_left_index, int in_right_index){
       if(in_left_index > in_right_index)  return null;
       // 根节点在中序遍历中的位置：in_root_index
       int in_root_index = map.get(preorder[pre_root_index]);
       // 创建一个根节点
       TreeNode node = new TreeNode(preorder[pre_root_index]);
       // 寻找node的左节点: 
       // 在前序遍历中的位置就是  根节点的下标 + 1（右边一个单位）
       // 在中序遍历中的位置就是： 1. 左边界不变，2. 右边界就是根节点的左边一个单位 in_root_index - 1
       node.left = rebuild(pre_root_index + 1, in_left_index, in_root_index - 1);
       // 寻找node的右节点: 
       // 在前序遍历中的位置就是  根节点的下标 + 左子树长度 + 1
       // 在中序遍历中的位置就是： 1. 左边界在根节点的右边一个单位  in_root_index + 1, 2. 右边界不变
       node.right = rebuild(pre_root_index + in_root_index - in_left_index + 1, in_root_index + 1, in_right_index);
       return node;
    }
}