首页 > 极客资料 博客日记
二叉树的 Morris 中序遍历——O(1)空间复杂度
2024-09-15 15:00:02极客资料围观21次
本篇文章分享二叉树的 Morris 中序遍历——O(1)空间复杂度,对你有帮助的话记得收藏一下,看极客之家收获更多编程知识
回顾
问题陈述: 给定一棵二叉树,实现中序遍历并返回包含其中序序列的数组
例如给定下列二叉树:
我们按照左、根、右的顺序递归遍历二叉树,得到以下遍历:
最终中序遍历结果可以输出为: [3, 1, 9, 2, 4, 7, 5, 8, 6]
Morris trick
Morris 中序遍历是一种树遍历算法,旨在实现 O(1) 的空间复杂度,无需递归或外部数据结构。该算法应高效地按中序顺序访问二叉树中的每个节点,并在遍历过程中打印或处理节点值,而无需使用堆栈或递归。
关键思想是在 current node 与其对应的 rightmost node 之间建立临时链接
先来看下中序遍历的过程:
做法讨论
节点的中序前驱是左子树中最右边的节点。因此,当我们遍历左子树时,我们会遇到一个右子节点为空的节点,这是该子树中的最后一个节点。因此,我们观察到一种模式,每当我们处于子树的最后一个节点时,如果右子节点指向空,我们就会移动到该子树的父节点。
当我们当前处于某个节点时,可能会出现以下情况:
情况1:当前节点没有左子树
- 打印当前节点的值
- 然后到当前节点的右子节点
如果没有左子树,我们只需打印当前节点的值,因为左侧没有节点可遍历。之后,我们移至右子节点继续遍历。
情况 2:存在一棵左子树,并且该左子树的最右边的孩子指向空。
- 将左子树的最右边的子节点设置为指向当前节点。
- 移动到当前节点的左子节点。
在这种情况下,我们还没有访问左子树。我们从左子树的最右节点到当前节点建立一个临时链接。此链接可帮助我们稍后确定何时完成左子树的按序遍历。设置链接后,我们移至左子节点以探索左子树。
情况3:存在一棵左子树,并且该左子树的最右边的孩子已经指向当前节点。
- 打印当前节点的值
- 恢复临时链接(将其设置回空)
- 移动到当前节点的右子节点。
这种情况对于保持树结构的完整性至关重要。如果左子树的最右边的子节点已经指向当前节点,则意味着我们已经完成了左子树的按序遍历。我们打印当前节点的值,然后恢复临时链接以恢复原始树结构。最后,我们移动到右子节点继续遍历。
算法
步骤 1:初始化 current 来遍历树。将 current 设置为二叉树的根。
步骤 2:当前节点不为空时:如果当前节点没有左子节点,则打印当前节点的值并移动到右子节点,即将当前节点设置为其右子节点。
步骤 3: 当前节点有左孩子,我们找到当前节点的 in-order predecessor 。这个 in-order predecessor 是左子树的最右节点。
- 如果 in-order predecessor 的右孩子节点为空:
- 将 in-order predecessor 右孩子节点设置为当前节点。
- 移动到 current 的左孩子
- 如果 in-order predecessor 的右孩子不为空:
- 通过in-order predecessor 的右孩子设置为空
- 打印当前节点的值。
- 通过先前 in-order predecessor 的右孩子拿到 current , 然后移动到 cuurent 的右孩子节点
重复步骤 2 和 3,直到到达树的末尾。
代码实现
#include <iostream>
#include <sstream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <map>
using namespace std;
// TreeNode structure
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
// Function to perform iterative Morris
// inorder traversal of a binary tree
vector<int> getInorder(TreeNode* root) {
// Vector to store the
// inorder traversal result
vector<int> inorder;
// Pointer to the current node,
// starting from the root
TreeNode* cur = root;
// Loop until the current
// node is not NULL
while (cur != NULL) {
// If the current node's
// left child is NULL
if (cur->left == NULL) {
// Add the value of the current
// node to the inorder vector
inorder.push_back(cur->val);
// Move to the right child
cur = cur->right;
} else {
// If the left child is not NULL,
// find the predecessor (rightmost node
// in the left subtree)
TreeNode* prev = cur->left;
while (prev->right && prev->right != cur) {
prev = prev->right;
}
// If the predecessor's right child
// is NULL, establish a temporary link
// and move to the left child
if (prev->right == NULL) {
prev->right = cur;
cur = cur->left;
} else {
// If the predecessor's right child
// is already linked, remove the link,
// add current node to inorder vector,
// and move to the right child
prev->right = NULL;
inorder.push_back(cur->val);
cur = cur->right;
}
}
}
// Return the inorder
// traversal result
return inorder;
}
};
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->left->right->right = new TreeNode(6);
Solution sol;
vector<int> inorder = sol.getInorder(root);
cout << "Binary Tree Morris Inorder Traversal: ";
for(int i = 0; i< inorder.size(); i++){
cout << inorder[i] << " ";
}
cout << endl;
return 0;
}
版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
标签:
相关文章
最新发布
- Nuxt.js 应用中的 prerender:routes 事件钩子详解
- 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间的问题
- 【FAQ】HarmonyOS SDK 闭源开放能力 —Vision Kit
- 六、Spring Boot集成Spring Security之前后分离认证流程最佳方案
- 《JVM第7课》堆区
- .NET 8 高性能跨平台图像处理库 ImageSharp
- 还在为慢速数据传输苦恼?Linux 零拷贝技术来帮你!
- 刚毕业,去做边缘业务,还有救吗?
- 如何避免 HttpClient 丢失请求头:通过 HttpRequestMessage 解决并优化
- 让性能提升56%的Vue3.5响应式重构之“版本计数”