XingHuiSamaの宝藏之地

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

‍

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

‍

1. 算法核心思想：双剑合璧

这道题是二叉树构建类的“终极大Boss”，它的核心逻辑在于彻底弄懂两种遍历方式的终极使命：

前序遍历（Preorder）的使命：提供“根节点”。 前序遍历的顺序是“根 -> 左 -> 右”。这意味着，无论当前是在整棵树还是某棵子树中，前序数组的第 1 个元素，绝对是当前的根节点！
中序遍历（Inorder）的使命：提供“领地边界”。 中序遍历的顺序是“左 -> 根 -> 右”。只要我们知道了当前的根节点是谁，去中序数组里找到它的位置（mid），它左边的所有数字就全都是左子树的成员，右边的所有数字就全都是右子树的成员。

核心解题步骤（分治法）：

从 preorder 中揪出第 1 个数字，当做总根节点。
去 inorder 中查出这个数字的位置，把数组切成左右两半。
把左半边交给左递归去建树，把右半边交给右递归去建树。

‍
‍

2. 代码逻辑拆解

主控函数 buildTree：
- 提前布阵（哈希表）：如果每次都在中序数组里用 for 循环找根节点，太慢了。我们直接开辟一个哈希表 map，把中序数组里的 [值 -> 索引] 全部登记在册。以后不管找谁，瞬间就能拿到它的坐标。
- 启动外包：调用核心递归函数 func，传入合法的双端闭区间 [0, size() - 1]。
核心施工队 func：
- 防坠崖（Base Case）：if (right < left)。当区间彻底错乱（说明里面没数字了），立刻返回空指针 NULL。
- 立根节点：当前树的根节点，就是 preorder[0]。立刻把它 new 出来。
- 定位切分点：去查字典 map，找出根节点在中序数组里的坐标 mid。
- 吃掉用过的根节点：这里用了非常直观的 preorder.erase(preorder.begin() + 0);。既然根节点已经被我们揪出来了，就把它从前序数组里删掉，这样下一次递归时，新的根节点自然就会“顶”到第 1 个位置！
- 下放权力（递归）：
  - 左子树的领地是 [left, mid - 1]，调用 func 去建树。
  - 右子树的领地是 [mid + 1, right]，调用 func 去建树。
- 向上汇报：把建好的 node 返回给上级。

‍

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> map;
        for (int i = 0;i < inorder.size();i++) {
            map[inorder[i]] = i;
        }

        TreeNode* node = func(map,preorder,inorder,0,inorder.size()-1);
        return node;
    }
    TreeNode* func(unordered_map<int, int>& map,vector<int>& preorder, vector<int>& inorder, int left, int right) {
        if (right < left) {
            return NULL;
        }
        TreeNode* node = new TreeNode(preorder[0]);

        int mid = map[preorder[0]];

        preorder.erase(preorder.begin() + 0);

        node->left = func(map,preorder,inorder,left,mid-1);
        node->right = func(map,preorder,inorder,mid+1,right);
        return node;
    }
};

3. 复杂度分析

空间复杂度：O**(N)**。哈希表 map 存储了 N 个节点的位置信息，递归系统栈最深为 N 层。

‍