- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
问题陈述: 给定一棵二叉树,实现中序遍历并返回包含其中序序列的数组 例如给定下列二叉树: 我们按照左、根、右的顺序递归遍历二叉树,得到以下遍历: 最终中序遍历结果可以输出为: [3, 1, 9, 2, 4, 7, 5, 8, 6] 。
Morris 中序遍历是一种树遍历算法,旨在实现 O(1) 的空间复杂度,无需递归或外部数据结构。该算法应高效地按中序顺序访问二叉树中的每个节点,并在遍历过程中打印或处理节点值,而无需使用堆栈或递归。 关键思想是在 current node 与其对应的 rightmost node 之间建立临时链接 先来看下中序遍历的过程:
节点的中序前驱是左子树中最右边的节点。因此,当我们遍历左子树时,我们会遇到一个右子节点为空的节点,这是该子树中的最后一个节点。因此,我们观察到一种模式,每当我们处于子树的最后一个节点时,如果右子节点指向空,我们就会移动到该子树的父节点.
当我们当前处于某个节点时,可能会出现以下情况:
情况1:当前节点没有左子树 。
情况 2:存在一棵左子树,并且该左子树的最右边的孩子指向空.
情况3:存在一棵左子树,并且该左子树的最右边的孩子已经指向当前节点.
步骤 1:初始化 current 来遍历树。将 current 设置为二叉树的根。 步骤 2:当前节点不为空时:如果当前节点没有左子节点,则打印当前节点的值并移动到右子节点,即将当前节点设置为其右子节点。 步骤 3: 当前节点有左孩子,我们找到当前节点的 in-order predecessor 。这个 in-order predecessor 是左子树的最右节点.
#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;
}
最后此篇关于二叉树的Morris中序遍历——O(1)空间复杂度的文章就讲到这里了,如果你想了解更多关于二叉树的Morris中序遍历——O(1)空间复杂度的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
运行 Tomcat 失败并出现 java.lang.OutOfMemoryError - 与缺少 PermGen 空间相关的错误。 我最近将 Tomcat 更改为以自己的用户(而非 root)运行。
我们有一个表,其中包含数百万行,其中包含 PostGIS 几何图形。我们要执行的查询是:落在边界几何内的最新条目是什么?这个查询的问题是我们经常会有大量的项目匹配边界框(半径大约为 5 公里),然后
我有一个Elasticsearch设置,它将允许用户搜索通配符作为索引。 array:3 [ "index" => "users" "type" => "user" "body" => arra
我创建了一个表,其中每行包含两个按钮,并且两个按钮连接在一起,我想将两个按钮分开。我用过 不起作用,css 也是,这是他们的另一种方式。 我有另一个问题,因为我不想在表格边框内显示操作按钮,而是在靠近
我试图在 jQuery Mobile 中的两个按钮之间留出空白。现实中的布局是这样的: Button 1 Button 2 (Hidden w/ display: none)
按照目前的情况,这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the
您好,我对图表应用程序还很陌生。现在我为我的应用程序创建了条形图。当我运行 create bar chart as separate project 时,输出如下所示。 然后当我将条形图与我的应用程序
我在使用 H2 和 GeoDB(内存中,junit)时遇到问题。 另外,使用 Hibernate 5(每个包的最新版本,包括 hibernate-spatial)和 Spring 4。 通过 id 实
我想画一张澳大利亚的 map ,并将每个城市表示为一个点。 然后突出显示人口众多(> 1M)的城市 library(sp) library(maps) data(canada.cities) head
关闭。这个问题是opinion-based .它目前不接受答案。 想改进这个问题?更新问题,以便 editing this post 提供事实和引用来回答它. 6年前关闭。 Improve this
如何保持.txt文件中存在的空格?在.txt文件中,它表示: text :text text1 :text1 text23 :text2 text345 :text3 如果我写这段
以下哪个键最大? 选项 1:16 个数字 [0,9] 选项 2:30 个元音 选项 3:字母表中的 16 个字母 选项 4:32 位 有人可以帮助我,告诉我哪一个是正确的答案以及我们如何计算它吗?我知
在 Unity 3d 中使用 Azure 空间 anchor 来实现在 iOS 和 Android 上部署的室内和室外增强现实体验是否有益? 最佳答案 是的,对于 Azure Spatial Anch
我有一个绝对定位的圆形图像。图像只需占据屏幕宽度的 17%,并且距离顶部 5 个像素。 问题是,当我调整图像大小以占据屏幕宽度的 17% 时,它会这样做,但同时容器会变长。图像本身不会拉伸(stret
我在 Ubuntu 14.04 上使用 Cassandra。从文档中,我可以看到运行命令: nodetool snapshot 创建我的 key 空间的快照。 命令的输出是: nodetool sn
Heroku引入了“私有(private)空间”,是否可以将现有应用迁移到私有(private)空间? https://blog.heroku.com/archives/2015/9/10/herok
是否允许在语义记录中使用非绑定(bind)空格 或其他 HTML 编码字符?我遇到的问题是 ; 字符被软件视为记录的结尾。 例如:假设我有一份婚姻记录,其中包含 2 个结婚者的姓氏、结婚年份以及结
我正在研究“智能 parking ”项目,偶然发现了包含我们真正需要的YouTube视频。我们已经实现了第一部分,即从视频源进行实时透视变换,下一步是将其定义为一组矩形 我基本上需要知道他是如何做到的
我有两个类:Engine 和 Trainset(多个单元),这两个类共享其 ID 空间,其中包含名称和系列 id=- . 这是我的Engine类(它是抽象的,因为有引擎的子类型(DieselEngin
如果有人能帮助我,那就太好了。 我正在尝试使用Java的Split命令,使用空格分割字符串,但问题是,字符串可能没有空格,这意味着它将只是一个简单的顺序(而不是“输入2”将是“退出”) Scanner
我是一名优秀的程序员,十分优秀!