首页 > 其他 > 详细

Morris遍历

时间:2020-07-12 11:47:49      阅读:60      评论:0      收藏:0      [点我收藏+]
 1 // 1、如果当前节点没有左儿子,则打印当前节点的值,然后进入右子树;
 2 // 2、如果当前节点有左儿子,则找当前节点的前驱。
 3 //   (1) 如果前驱节点的右儿子为空,说明左子树没遍历过,则进入左子树遍历,并将前驱节点的右儿子置成当前节点,方便回溯;
 4 //   (2) 如果前驱节点的右儿子为当前节点,说明左子树已被遍历过,则将前驱节点的右儿子恢复为空,然后打印当前节点的值,然后进入右子树继续遍历;
 5 class Solution 
 6 {
 7 public:
 8     void recoverTree(TreeNode* root) 
 9     {
10         while (root) 
11         {
12             if (!root->left) 
13             {
14                 cout << root->val << endl;
15                 root = root->right;
16             } 
17             else 
18             {
19                 auto p = root->left;
20                 while (p->right && p->right != root) p = p->right;
21                 
22                 if (!p->right) p->right = root, root = root->left;
23                 else 
24                 {
25                     p->right = NULL;
26                     cout << root->val << endl;
27                     root = root->right;
28                 }
29             }
30         }
31     }
32 };

 

Morris遍历

原文:https://www.cnblogs.com/yuhong1103/p/13287110.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!