105. 从前序与中序遍历序列构造二叉树

中等

相关标签

premium lock icon相关企业

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

示例 1:

img

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

示例 2:

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

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
private:
    unordered_map<int, int> index;

public:
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
        
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = index[preorder[preorder_root]];
        
        // 先把根节点建立出来
        TreeNode* root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        // 构造哈希映射，帮助我们快速定位根节点
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

// 作者：力扣官方题解
// 链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/255811/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

核心思路（一句话）

前序遍历的第一个元素是当前子树的根节点；在中序遍历中找到这个根节点后，根左侧是左子树、右侧是右子树。把左右子树在先序/中序里的区间算清楚后，递归构造即可。

代码主要部分与含义

1
2
private:
    unordered_map<int, int> index;
  • index：把中序遍历值 -> 下标 的哈希表，作用是 O(1) 定位某个值在中序序列中的位置（避免每次线性查找）。
1
2
3
TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder,
                      int preorder_left, int preorder_right,
                      int inorder_left, int inorder_right)
  • myBuildTree：递归函数，负责构造区间 [preorder_left, preorder_right]（先序）和 [inorder_left, inorder_right]（中序）所描述的子树，并返回该子树的根指针。
  • 这两个区间一一对应，代表 同一棵子树 在先序与中序中的范围。
1
2
3
if (preorder_left > preorder_right) {
    return nullptr;
}
  • 终止条件：如果先序区间为空（左界大于右界），说明没有节点，返回 nullptr。
1
2
int preorder_root = preorder_left;
int inorder_root = index[preorder[preorder_root]];
  • preorder_root：先序区间的第一个位置就是当前子树的根在先序中的下标。
  • inorder_root：通过哈希表得到根在中序数组中的下标。
1
TreeNode* root = new TreeNode(preorder[preorder_root]);
  • 新建根节点，值为 preorder[preorder_root]。
1
int size_left_subtree = inorder_root - inorder_left;
  • 关键：左子树节点数等于中序区间中从 inorder_left 到 inorder_root-1 的元素个数，所以 size_left_subtree = inorder_root - inorder_left。
1
2
3
4
5
root->left = myBuildTree(preorder, inorder,
                         preorder_left + 1,
                         preorder_left + size_left_subtree,
                         inorder_left,
                         inorder_root - 1);
  • 构造左子树：
    • 先序中，根节点后面 size_left_subtree 个节点属于左子树，所以先序左子树区间是 [preorder_left+1, preorder_left+size_left_subtree]。
    • 中序左子树区间是 [inorder_left, inorder_root-1]。
1
2
3
4
5
root->right = myBuildTree(preorder, inorder,
                          preorder_left + size_left_subtree + 1,
                          preorder_right,
                          inorder_root + 1,
                          inorder_right);
  • 构造右子树：
    • 先序右子树区间从 preorder_left + size_left_subtree + 1 开始到 preorder_right 结束（跳过根和左子树的元素）。
    • 中序右子树区间是 [inorder_root+1, inorder_right]。

最后 return root; 把建好的子树返回。

1
2
3
4
5
6
7
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = preorder.size();
    for (int i = 0; i < n; ++i) {
        index[inorder[i]] = i;
    }
    return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
  • 入口函数：先建哈希表 index（中序值到下标），然后对整棵树的区间 [0,n-1] 调用递归构造。

具体例子（手把手走一次）

设

  • preorder = [3, 9, 20, 15, 7]
  • inorder = [9, 3, 15, 20, 7]

入口：myBuildTree(..., preorder_left=0, preorder_right=4, inorder_left=0, inorder_right=4)

  1. 根是 preorder[0] = 3。在中序中 3 的下标 inorder_root = 1（因为 inorder = [9,3,15,20,7]）。
  2. 左子树节点数 size_left_subtree = inorder_root - inorder_left = 1 - 0 = 1。
  3. 左子树区间：
    • 先序：[preorder_left+1, preorder_left+size_left_subtree] = [1,1]（元素 [9]）
    • 中序：[inorder_left, inorder_root-1] = [0,0]（元素 [9]）
      递归会创建节点 9，它没有子节点（因为左右区间会变为空）。
  4. 右子树区间：
    • 先序：[preorder_left + size_left_subtree + 1, preorder_right] = [2,4]（元素 [20,15,7]）
    • 中序：[inorder_root+1, inorder_right] = [2,4]（元素 [15,20,7]）
      递归下来会把 20 作为根，15 为其左子、7 为其右子 —— 最终得到与 LeetCode 示例相同的树。

这个例子显示了“先序第一个是根；用中序定位根；确定左子树节点数；在先序中切出对应的左/右区间” 的完整流程。

为什么用哈希表 index

每次需要在中序数组中查找根的位置，如果用线性查找，最坏情况下每次查找是 O(n)，递归中会有 O(n) 次查找导致 O(n^2) 时间。用哈希表把查找降到 O(1)，整体时间复杂度变成 O(n)。

复杂度分析

  • 时间复杂度：O(n)。每个节点被创建一次；构造哈希表 O(n)；递归处理每个节点常数工作。
  • 空间复杂度：O(n)。哈希表需要 O(n)，再加上递归栈最坏 O(n)（链状树时）。

注意事项与边界情况

  1. 元素必须互不相同：代码中将 inorder 的值映射到下标，若有重复值，哈希表中会覆盖且定位不唯一，算法会出错。题目通常保证节点值唯一。
  2. 空树：若 preorder 和 inorder 都为空，n=0，myBuildTree 的第一次调用会立刻返回 nullptr。
  3. 参数越界/不一致：调用前假设 preorder.size() == inorder.size()，且确实互为同一棵树的遍历序列。若输入不合法（长度不等或不匹配），行为未定义。
  4. 递归深度：极端情况下（退化为链表），递归深度为 n，可能导致栈溢出。可以改写为非递归或增加栈大小，视环境而定。

小结（要点回顾）

  • 先序第一个是根；在中序中定位根，划分左右子树区间。
  • size_left_subtree = inorder_root - inorder_left 是把“中序的划分”转成“先序的区间长度”的桥梁。
  • 用哈希表把中序定位从 O(n) 降到 O(1)，从而总体 O(n)。
  • 要求值唯一，递归区间要严格对应。