7.21 第一次做，无法 AC
7.22 不能一次 AC，明天再做做
7.23 不能 AC，明天再做做
7.25 无法 AC
7.28 无法 AC
7.29 一次 AC

题目描述

原题链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/submissions/

解题思路

K 神题解：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/

tip：K 神题解有个错误：

7.21 感悟：

• 递归的目的是左子树和右子树自己去重建二叉树，然后返回一个重建好的根节点给到最顶层的根节点！

• 这其实就是分治思想！左子树和右子树自己都解决好了再返回！

7.24 踩坑感悟：

• 第17行代码：left > right 才行，不能等于，等于的话，还是有节点，不能直接返回 null，要越过了才能返回 null ！

7.28 踩坑：

• 一样！！和 7.24 犯的同样的错误！left = right 的话还是可以建立当前的根节点！！！必须 left > right 实实在在的越过去了，才无法建立当前的根节点！

7.29 感悟：

• 关键是递归函数要传进去啥：前序遍历首个根节点的索引、中序遍历的左边界、中序遍历的右边界。

  class Solution {
    int[] preorder;
    Map<Integer, Integer> map = new HashMap<>();
    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 root, int left, int right) {
        // 这里 left 不能等于 right,等于的话，当前的根节点就是它本身
        if(left > right) return null; // 越过叶节点，那给上一个节点的左或右子节点一个 null 就行了
        // new 一个新的根节点作为重建二叉树后的根节点，用传进来的先序遍历数组的下标去获取值送去构造函数去 new。注意：preorder[root] 返回的是一个数值！！不是节点！所以可以作为构造函数的值传进去！
        TreeNode node = new TreeNode(preorder[root]);
        // 根据先序遍历的首元素传进来的下标去先序遍历数组中找到对应的元素，然后去中序遍历的哈希表中找到与先序遍历相等的节点，返回的值即中序遍历数组中根节点的索引，据其就可分出左右子树。
        int i = map.get(preorder[root]);
        node.left = recur(root + 1, left, i - 1);
        node.right = recur(root + (i - left) + 1, i + 1, right);
        return node;
    }
  }

  // 7.23 日注释版本
  class Solution {
    int[] preorder;
    Map<Integer, Integer> map = new HashMap<>();
    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(Integer root, Integer left, Integer right) {
        if(left > right) return null;
        // 根据先序遍历数组第一个元素，创建重建后二叉树的根节点
        TreeNode node = new TreeNode(preorder[root]);
        // 取出中序遍历中的根节点索引
        int i = map.get(preorder[root]);
        // 为根节点接上重建好的左右子树，用递归来分治左右子树
        node.left = recur(root + 1, left, i - 1);
        node.right = recur(root + (i - left) + 1, i + 1, right);
        return node;
    }
  }