数据结构与算法：Morris 遍历

一、原理

1.内容

（1）核心

没有左子树的节点只到达一次，有左子树的节点会到达两次，其中用左子树最右节点的右指针状态来标记第几次到达。

（2）过程

首先，开始时 cur 在头节点，cur 为空时整个过程停止。 若 cur 没有左孩子，就向右移动。 若 cur 有左孩子，就去找 cur 左子树的最右节点 mostRight。若 mostRight 的右指针为空，那么就让其指向 cur，然后 cur 向左移动。若 mostRight 右指针指向 cur，就让其指向空，然后 cur 向右移动。

首先 cur 肯定先来到 a 节点。之后，因为 a 节点有左孩子，那么就去 a 节点左子树的最右节点，所以就是 d 节点。因为此时 d 节点的右指针为空，所以让其指向 a 节点，然后 cur 来到 b 节点。 之后，因为 b 节点有左孩子，所以还是去找左子树的最右节点，那么就是 c 节点。同样因为此时 c 节点右指针为空，所以让其指向 b 节点，然后 cur 来到 c 节点。 当 cur 来到 c 节点时，因为没有左孩子，那么就向右移动，所以 cur 回到 b 节点。此时再去找左子树的最右节点，可以发现 c 节点的右指针指向自己，所以 c 节点的右指针指向空，然后 cur 往右去 d 节点。 之后因为没有左孩子，所以往右回到 a 节点，同样去找左子树的最右节点，发现 d 节点的右指针指回来了，所以将其指为空，cur 往右来到 e 节点。 之后就是把 f 节点的右指针指向 e，然后来到 f，之后回到 e，把 f 的右指针指回空，然后去 g，完成遍历。观察整个过程，不难发现时间复杂度就是 O(n) 的，空间复杂度 O(1)。

2.二叉树的前序遍历

class Solution { 
public: 
    vector<int> preorderTraversal(TreeNode* root) { 
        vector<int>ans; 
        return morrisPreorder(root,ans); 
    } 
    vector<int>morrisPreorder(TreeNode* head,vector<int>&ans) { 
        TreeNode* cur=head; 
        TreeNode* mostRight=NULL; 
        while(cur!=NULL) { 
            mostRight=cur->left; 
            if(mostRight!=NULL) { 
                while(mostRight->right!=NULL&&mostRight->right!=cur) { 
                    mostRight=mostRight->right; 
                } 
                if(mostRight->right==) { 
                    ans.(cur->val); 
                    mostRight->right=cur; 
                    cur=cur->left; 
                    ; 
                } 
                 { 
                    mostRight->right=; 
                } 
            } 
             { 
                ans.(cur->val); 
            } 
            cur=cur->right; 
        } 
         ans; 
    } 
};