首页 / 算法 / Morris 遍历二叉树
Morris 遍历二叉树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Morris 遍历二叉树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3304字，纯文字阅读大概需要5分钟。
内容图文
Morris Traversal 方法实现前序、中序以及后序遍历二叉树。相比使用栈或者递归（也是通过栈空间）方法，Morris 方法可以在空间复杂度为 O(1)，时间复杂度为 O(n) 的条件下实现对二叉树的遍历。
前序遍历
- 如果当前节点左孩子 cur->left 为空，输出当前节点 cur 并指向右孩子 cur->right。
- 如果当前节点左孩子 cur->left 不为空，那么在当前节点的左子树中找出前驱节点 pre，也就是左子树中最大的点。
- 如果前驱节点的右孩子 pre->right 为空，那么将右孩子指向当前节点。输出当前节点。当前节点更新为当前节点的左孩子。
- 如果前驱节点的右孩子 pre->right 不为空，也就是指向当前节点。重新将右孩子设为空。当前节点更新为当前节点的右孩子。
- 重复 1、2 直到当前节点为空。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
TreeNode* cur = root;
TreeNode* pre = NULL;
vector<int> result;
while(cur!=NULL){
if (cur->left == NULL){
result.push_back(cur->val);
cur = cur->right;
}else{
pre = cur->left;
while(pre->right!=NULL && pre->right!=cur){
pre = pre->right;
}
if (pre->right==NULL){
pre->right=cur;
result.push_back(cur->val);
cur = cur->left;
}else{
pre->right = NULL;
cur = cur->right;
}
}
}
return result;
}
};
中序遍历
- 如果当前节点左孩子 cur->left 为空，输出当前节点 cur 并指向右孩子 cur->right。
- 如果当前节点左孩子 cur->left 不为空，那么在当前节点的左子树中找出前驱节点 pre，也就是左子树中最大的点。
- 如果前驱节点的右孩子 pre->right 为空，那么将右孩子指向当前节点。当前节点更新为当前节点的左孩子。
- 如果前驱节点的右孩子 pre->right 不为空，也就是指向当前节点。重新将右孩子设为空。输出当前节点。当前节点更新为当前节点的右孩子。
- 重复 1、2 直到当前节点为空。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
TreeNode* cur = root;
TreeNode* pre = NULL;
vector<int> result;
while(cur!=NULL){
if (cur->left == NULL){
result.push_back(cur->val);
cur = cur->right;
}else{
pre = cur->left;
while(pre->right!=NULL && pre->right!=cur){
pre = pre->right;
}
if (pre->right == NULL){
pre->right=cur;
cur = cur->left;
}else{
pre->right = NULL;
result.push_back(cur->val);
cur = cur->right;
}
}
}
return result;
}
};
后序遍历
- 新增临时节点 dump，并且将 root 设为 dump 的左孩子。
- 如果当前节点左孩子 cur->left 为空，输出当前节点 cur 并指向右孩子 cur->right。
- 如果当前节点左孩子 cur->left 不为空，那么在当前节点的左子树中找出前驱节点 pre，也就是左子树中最大的点。
- 如果前驱节点的右孩子 pre->right 为空，那么将右孩子指向当前节点。当前节点更新为当前节点的左孩子。
- 如果前驱节点的右孩子 pre->right 不为空，也就是指向当前节点。逆序输出当前节点左孩子到前序节点的路径。重新将右孩子设为空。当前节点更新为当前节点的右孩子。
- 重复 2、3 直到当前节点为空。
逆序打印路径其实就是逆序打印单链表节点。先将单链表反转，然后依次打印，接下来重新反转到初始状态。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
TreeNode dump(-1);
dump.left = root;
TreeNode* cur = &dump;
TreeNode* pre = NULL;
vector<int> result;
while(cur!=NULL){
if (cur->left == NULL){
cur = cur->right;
}else{
pre = cur->left;
while(pre->right!=NULL && pre->right!=cur){
pre = pre->right;
}
if (pre->right == NULL){
pre->right=cur;
cur = cur->left;
}else{
printReverse(cur->left, pre, result);
pre->right = NULL;
cur = cur->right;
}
}
}
return result;
}
void printReverse(TreeNode* from, TreeNode* to, vector<int>& result){
Reverse(from, to);
TreeNode* p = to;
while(true){
result.push_back(p->val);
if(p == from){
break;
}
p = p->right;
}
Reverse(to, from);
}
void Reverse(TreeNode* from, TreeNode* to){
TreeNode* x = from;
TreeNode* y = from->right;
TreeNode* z;
if (from == to){
return;
}
x->right = NULL;
while(x != to){
z = y->right;
y->right = x;
x = y;
y = z;
}
}
};
总结
Morris 方法遍历之所以能够在 O(1) 的空间的条件下完成是因为它充分利用到叶子的左右孩子来记录上层关系，从而不需要额外的栈空间来记录顺序关系。通过三种遍历可以看到，其实总体上的代码逻辑没有发生改变，主要是改变了输出结果的时机和方式。
https://www.ouyangsong.com/posts/27490/
原文：https://www.cnblogs.com/ouyangsong/p/9348179.html
内容总结
以上是互联网集市为您收集整理的Morris 遍历二叉树全部内容，希望文章能够帮你解决Morris 遍历二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。