中资源 网站域名解析,国外做动运服装的网站,有口碑的app制作,汕头制作手机网站初始版本
这段代码实现了根据前序遍历和中序遍历重建二叉树。下面我将详细解释每一行的作用#xff0c;并逐步讲解算法的思路和运行步骤。 代码及注释 class Solution {public:// buildTree 函数用来根据前序遍历(pre)和中序遍历(in)重建二叉树TreeNode* buildTree(vector并逐步讲解算法的思路和运行步骤。 代码及注释 class Solution {public:// buildTree 函数用来根据前序遍历(pre)和中序遍历(in)重建二叉树TreeNode* buildTree(vectorint pre, vectorint 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])vectorint _pre(pre.begin() 1, pre.begin() i 1);vectorint _in(in.begin(), in.begin() i);// 划分出右子树的前序遍历 (pre[i1] 到 pre.end) 和中序遍历 (in[i1] 到 in.end)vectorint pre_(pre.begin() i 1, pre.end());vectorint 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 个元素。
• 右子树的前序遍历是前序遍历的第 i1 到最后一个元素。
• 右子树的中序遍历是中序遍历的第 i1 到最后一个元素。
5. 递归结束条件
• 当没有更多元素可以划分时递归会返回 nullptr。
注意 这是一个构造新的 vectorint 的方法使用的是 迭代器范围 的方式来构建子数组。具体来说这里涉及到 1. pre.begin() 1
• pre.begin() 返回 pre 数组的第一个元素的迭代器。
• pre.begin() 1 表示跳过数组的第一个元素指向第二个元素即 pre[1]。 2. pre.begin() i 1
• pre.begin() i 1 表示从 pre 数组的第 i1 个元素的迭代器开始注意这并不包括 pre[i1] 之前的元素。
• 例如如果 i 1pre.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_mapint, int inOrderMap;TreeNode* buildTree(vectorint pre, vectorint 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 vectorint 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_mapint, 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_mapint, 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)。
