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;
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)
1
2
3
if (preorder_left > preorder_right) {
    return nullptr;
}
1
2
int preorder_root = preorder_left;
int inorder_root = index[preorder[preorder_root]];
1
TreeNode* root = new TreeNode(preorder[preorder_root]);
1
int 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);
1
2
3
4
5
root->right = myBuildTree(preorder, inorder,
                          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);
}

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

设

入口：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)。

复杂度分析

注意事项与边界情况

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

小结（要点回顾）