LeetCodehot 力扣热题100 从前序与中序遍历序列构造二叉树

初始版本

这段代码实现了根据前序遍历和中序遍历重建二叉树。下面我将详细解释每一行的作用，并逐步讲解算法的思路和运行步骤。

代码及注释

class Solution {public:// buildTree 函数用来根据前序遍历(pre)和中序遍历(in)重建二叉树TreeNode* buildTree(vector<int>& pre, vector<int>& in){// 基本情况：当前序或中序遍历为空时，返回 nullptrif (pre.empty() || in.empty()) return nullptr;// 创建根节点，根节点的值是前序遍历中的第一个元素TreeNode* subroot = new TreeNode(pre[0]);// 在中序遍历中找到根节点的位置，根节点就是前序遍历的第一个元素for (int i = 0; i < in.size(); i++) {// 如果中序遍历的第 i 个元素等于前序遍历的第一个元素，说明找到了根节点if (in[i] == pre[0]) {// 划分出左子树的前序遍历 (pre[1] 到 pre[i]) 和中序遍历 (in[0] 到 in[i-1])vector<int> _pre(pre.begin() + 1, pre.begin() + i + 1);vector<int> _in(in.begin(), in.begin() + i);// 划分出右子树的前序遍历 (pre[i+1] 到 pre.end) 和中序遍历 (in[i+1] 到 in.end)vector<int> pre_(pre.begin() + i + 1, pre.end());vector<int> in_(in.begin() + i + 1, in.end());// 递归地建立左子树和右子树subroot->left = buildTree(_pre, _in);subroot->right = buildTree(pre_, in_);break; // 找到根节点后退出循环}}// 返回构建好的子树根节点return subroot;}};

思路分析

1. 基本情况：

• 当前序遍历 (pre) 或中序遍历 (in) 为空时，说明这部分子树不存在，直接返回 nullptr。

2. 创建根节点：

• 前序遍历的第一个元素即为当前子树的根节点。我们用这个值创建一个新的节点 subroot。

3. 找到根节点的位置：

• 在中序遍历 in 中，找到当前根节点（即前序遍历中的第一个元素）的索引 i。

• 中序遍历的特点是：根节点左边是左子树的元素，右边是右子树的元素。所以我们可以通过根节点的位置将 in 和 pre 数组分成两部分，分别对应左子树和右子树。

4. 递归构建左右子树：

• 左子树的前序遍历是前序遍历的第 1 到第 i 个元素（因为前序遍历中，根节点是第一个元素，左子树的元素紧接着根节点）。

• 左子树的中序遍历是中序遍历的第 0 到第 i-1 个元素。

• 右子树的前序遍历是前序遍历的第 i+1 到最后一个元素。

• 右子树的中序遍历是中序遍历的第 i+1 到最后一个元素。

5. 递归结束条件：

• 当没有更多元素可以划分时，递归会返回 nullptr。

注意

这是一个构造新的 vector<int> 的方法，使用的是 迭代器范围 的方式来构建子数组。具体来说，这里涉及到：

1. pre.begin() + 1

• pre.begin() 返回 pre 数组的第一个元素的迭代器。

• pre.begin() + 1 表示跳过数组的第一个元素，指向第二个元素，即 pre[1]。

2. pre.begin() + i + 1

• pre.begin() + i + 1 表示从 pre 数组的第 i+1 个元素的迭代器开始，注意这并不包括 pre[i+1] 之前的元素。

• 例如，如果 i = 1，pre.begin() + i + 1 就是 pre[2]（即 20）

假设前序遍历 pre = [3, 9, 20, 15, 7]，在第一次递归中，i = 1。根据上面的划分：

• pre.begin() + 1 指向 9。

• pre.begin() + i + 1 指向 20。

所以，pre.begin() + 1 到 pre.begin() + i + 1 的范围实际上是 [9]，而不是 [9, 20]，因为这就是 pre[1] 到 pre[1] 之间的范围。

运行步骤（举例）

假设给定前序遍历和中序遍历如下：

• 前序遍历 (pre): [3, 9, 20, 15, 7]

• 中序遍历 (in): [9, 3, 15, 20, 7]

第一步：

• 根节点是前序遍历的第一个元素：3。

• 在中序遍历中找到 3，它的位置是 1。

• 左子树的中序遍历：[9]。

• 右子树的中序遍历：[15, 20, 7]。

第二步：

• 左子树的前序遍历是 [9]，中序遍历是 [9]。

• 递归构建左子树：

• 根节点是 9，左右子树为空，返回节点 9。

第三步：

• 右子树的前序遍历是 [20, 15, 7]，中序遍历是 [15, 20, 7]。

• 根节点是 20。

• 在中序遍历中找到 20，它的位置是 1。

• 左子树的中序遍历是 [15]。

• 右子树的中序遍历是 [7]。

第四步：

• 左子树的前序遍历是 [15]，中序遍历是 [15]。

• 递归构建左子树：

• 根节点是 15，左右子树为空，返回节点 15。

第五步：

• 右子树的前序遍历是 [7]，中序遍历是 [7]。

• 递归构建右子树：

• 根节点是 7，左右子树为空，返回节点 7。

最终结果：

构建的二叉树如下：

        3

       / \

      9  20

         /  \

        15   7

时间复杂度

• 在每一层递归中，我们需要查找当前根节点在中序遍历中的位置，这需要 O(n) 时间（n 是当前子树的大小）。

• 总共有 O(n) 层递归，故总的时间复杂度是 O(n^2)，其中 n 是节点数。

空间复杂度

• 每次递归中需要创建新的数组用于存储左子树和右子树的前序遍历和中序遍历，空间复杂度是 O(n)。

如果可以优化查找中序位置的过程，可以将时间复杂度降低到 O(n)。

优化方案

优化的思路：

为了降低时间复杂度，我们可以利用哈希表（unordered_map）来存储每个元素在中序遍历中的位置，这样在查找根节点的位置时，就可以在 O(1) 的时间内完成查找。

优化后的步骤：

1. 创建哈希表：在开始构建二叉树之前，先遍历一次中序遍历数组，将每个元素的值与它的索引建立映射。这允许我们在递归过程中直接通过哈希表找到根节点在中序遍历中的位置，从而避免每次都要遍历整个中序数组。

2. 递归时直接访问位置：通过哈希表可以在 O(1) 时间内找到当前根节点在中序遍历中的位置，从而使得每次递归只需要 O(1) 时间来分割数组，避免了 O(n) 的查找操作。

优化后的代码：

class Solution {public:// 哈希表用于存储中序遍历每个元素的索引unordered_map<int, int> inOrderMap;TreeNode* buildTree(vector<int>& pre, vector<int>& in) {// 初始化哈希表for (int i = 0; i < in.size(); ++i) {inOrderMap[in[i]] = i;}// 调用递归函数，初始时传入前序遍历的全部元素return build(pre, 0, pre.size() - 1, 0, in.size() - 1);}TreeNode* build(const vector<int>& pre, int preStart, int preEnd, int inStart, int inEnd) {// 递归出口：如果当前子树的范围为空if (preStart > preEnd || inStart > inEnd) {return nullptr;}// 当前子树的根节点是前序遍历中的第一个元素TreeNode* root = new TreeNode(pre[preStart]);// 获取当前根节点在中序遍历中的位置int rootIndexInInOrder = inOrderMap[pre[preStart]];// 左子树的元素数量int leftSize = rootIndexInInOrder - inStart;// 递归构建左子树root->left = build(pre, preStart + 1, preStart + leftSize, inStart, rootIndexInInOrder - 1);// 递归构建右子树root->right = build(pre, preStart + leftSize + 1, preEnd, rootIndexInInOrder + 1, inEnd);return root;}};

解释：

1. 哈希表的构建：

• 在 buildTree 函数中，首先我们创建一个 unordered_map<int, int> inOrderMap 来存储中序遍历中每个元素的索引。

• 通过一次遍历中序数组，我们将元素和它们的索引存入哈希表。这个过程的时间复杂度是 O(n)。

2. 递归函数 build：

• 该函数接受前序遍历的子数组范围 preStart 到 preEnd 和中序遍历的子数组范围 inStart 到 inEnd。

• 每次递归从前序遍历中取出一个元素作为根节点，通过哈希表在 O(1) 时间内找到该根节点在中序遍历中的索引。

• 然后，根据根节点的位置将数组分成左子树和右子树，并递归构建左右子树。

3. 递归过程：

• 在构建每个子树时，计算左子树的大小 leftSize，并使用前序遍历的下一个元素作为左子树的根节点，递归地构建左子树和右子树。

时间复杂度：

• 创建哈希表：这一步需要遍历整个中序数组，时间复杂度是 O(n)。

• 递归构建树：每次递归操作仅需 O(1) 时间来查找根节点的位置，并且每个节点都会被访问一次，因此总的时间复杂度是 O(n)。

因此，优化后的算法的总时间复杂度是 O(n)。

好的，下面我将详细解释优化后的代码的运行步骤，展示如何通过前序遍历和中序遍历重建二叉树，特别是在使用哈希表优化查找操作之后。

我们仍然使用以下例子：

• 前序遍历 (pre): [3, 9, 20, 15, 7]

• 中序遍历 (in): [9, 3, 15, 20, 7]

1. 哈希表的构建

首先，我们构建一个哈希表 inOrderMap 来存储中序遍历每个元素的索引。遍历一次中序数组：

unordered_map<int, int> inOrderMap;

for (int i = 0; i < in.size(); ++i) {

    inOrderMap[in[i]] = i;

}

结果：

inOrderMap = {

    9: 0,

    3: 1,

    15: 2,

    20: 3,

    7: 4

};

这个哈希表允许我们在 O(1) 时间内找到任意元素在中序遍历中的位置。

2. 递归构建树的过程

接下来，我们通过递归构建二叉树。递归函数 build 的参数是：

• pre：前序遍历数组。

• preStart 和 preEnd：当前子树在前序遍历中的范围。

• inStart 和 inEnd：当前子树在中序遍历中的范围。

初始调用：

build(pre, 0, pre.size() - 1, 0, in.size() - 1);

也就是 preStart = 0, preEnd = 4, inStart = 0, inEnd = 4，这表示我们要构建整个二叉树。

第一步：构建根节点

1. 根节点：当前子树的根节点是前序遍历的第一个元素 pre[preStart] = 3。

所以当前树的根节点是 3。

2. 查找根节点位置：在中序遍历 [9, 3, 15, 20, 7] 中，通过哈希表，我们可以直接在 O(1) 时间内找到 3 的位置 inOrderMap[3] = 1。

3. 计算左子树大小：根据根节点的位置，左子树的元素数量是 rootIndexInInOrder - inStart = 1 - 0 = 1。

4. 递归构建左右子树：

• 左子树的前序遍历是 [9]，中序遍历是 [9]。

• 右子树的前序遍历是 [20, 15, 7]，中序遍历是 [15, 20, 7]。

递归调用：

• 构建左子树：build(pre, 1, 1, 0, 0)。

• 构建右子树：build(pre, 2, 4, 2, 4)。

第二步：构建左子树

左子树的递归调用 build(pre, 1, 1, 0, 0)：

1. 根节点：当前子树的根节点是 pre[preStart] = 9。

所以当前左子树的根节点是 9。

2. 查找根节点位置：在中序遍历 [9] 中，通过哈希表找到 9 的位置 inOrderMap[9] = 0。

3. 计算左子树大小：左子树的元素数量是 rootIndexInInOrder - inStart = 0 - 0 = 0。

4. 递归构建左右子树：

• 左子树的前序遍历是 []，中序遍历是 []。

• 右子树的前序遍历是 []，中序遍历是 []。

递归调用：

• 构建左子树：build(pre, 2, 1, 0, -1)，返回 nullptr（空树）。

• 构建右子树：build(pre, 2, 1, 1, 0)，返回 nullptr（空树）。

左子树构建完成，返回节点 9。

第三步：构建右子树

右子树的递归调用 build(pre, 2, 4, 2, 4)：

1. 根节点：当前子树的根节点是 pre[preStart] = 20。

所以当前右子树的根节点是 20。

2. 查找根节点位置：在中序遍历 [15, 20, 7] 中，通过哈希表找到 20 的位置 inOrderMap[20] = 3。

3. 计算左子树大小：左子树的元素数量是 rootIndexInInOrder - inStart = 3 - 2 = 1。

4. 递归构建左右子树：

• 左子树的前序遍历是 [15]，中序遍历是 [15]。

• 右子树的前序遍历是 [7]，中序遍历是 [7]。

递归调用：

• 构建左子树：build(pre, 3, 3, 2, 2)。

• 构建右子树：build(pre, 4, 4, 4, 4)。

第四步：构建左子树（右子树的左子树）

左子树的递归调用 build(pre, 3, 3, 2, 2)：

1. 根节点：当前子树的根节点是 pre[preStart] = 15。

所以当前左子树的根节点是 15。

2. 查找根节点位置：在中序遍历 [15] 中，通过哈希表找到 15 的位置 inOrderMap[15] = 2。

3. 计算左子树大小：左子树的元素数量是 rootIndexInInOrder - inStart = 2 - 2 = 0。

4. 递归构建左右子树：

• 左子树的前序遍历是 []，中序遍历是 []。

• 右子树的前序遍历是 []，中序遍历是 []。

递归调用：

• 构建左子树：build(pre, 4, 3, 2, 1)，返回 nullptr（空树）。

• 构建右子树：build(pre, 4, 3, 3, 2)，返回 nullptr（空树）。

左子树构建完成，返回节点 15。

第五步：构建右子树（右子树的右子树）

右子树的递归调用 build(pre, 4, 4, 4, 4)：

1. 根节点：当前子树的根节点是 pre[preStart] = 7。

所以当前右子树的根节点是 7。

2. 查找根节点位置：在中序遍历 [7] 中，通过哈希表找到 7 的位置 inOrderMap[7] = 4。

3. 计算左子树大小：左子树的元素数量是 rootIndexInInOrder - inStart = 4 - 4 = 0。

4. 递归构建左右子树：

• 左子树的前序遍历是 []，中序遍历是 []。

• 右子树的前序遍历是 []，中序遍历是 []。

递归调用：

• 构建左子树：build(pre, 5, 4, 4, 3)，返回 nullptr（空树）。

• 构建右子树：build(pre, 5, 4, 5, 4)，返回 nullptr（空树）。

右子树构建完成，返回节点 7。

最终结果

经过所有递归调用，我们最终得到了以下的二叉树：

        3

       / \

      9   20

          /  \

         15   7

总结

通过哈希表优化查找根节点在中序遍历中的位置，我们将每次递归中的查找操作的时间复杂度降低为 O(1)，使得整体的时间复杂度从 O(n²) 优化到了 O(n)。