数据结构与算法：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==NULL) { 
                    ans.push_back(cur->val); 
                    mostRight->right=cur; 
                    cur=cur->left; 
                    continue; 
                } 
                else { 
                    mostRight->right=NULL; 
                } 
            } 
            else { 
                ans.push_back(cur->val); 
            } 
            cur=cur->right; 
        } 
        return ans; 
    } 
};

先序遍历就是在 morris 遍历的过程中，只在第一次来到时打印该节点，第二次来到时不打印。而观察 morris 遍历的特点，当最右节点的右指针是 cur，那么就说明此时是第二次来到这个节点，所以就不打印。

3.二叉树的中序遍历

class Solution { 
public: 
    vector<int> inorderTraversal(TreeNode* root) { 
        vector<int>ans; 
        return morrisInorder(root,ans); 
    } 
    vector<int>morrisInorder(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==NULL) { 
                    mostRight->right=cur; 
                    cur=cur->left; 
                    continue; 
                } 
                else { 
                    ans.push_back(cur->val); 
                    mostRight->right=NULL; 
                } 
            } 
            else { 
                ans.push_back(cur->val); 
            } 
            cur=cur->right; 
        } 
        return ans; 
    } 
};

中序遍历就是在 morris 遍历的过程中，若只来一次，那么就直接打印，否则就在第二次来的时候再打印。根据 morris 遍历，有左子树的节点会来两遍，所以如果没有就直接打印，有的话就在最右节点右指针指向自己时输出。

4.二叉树的后序遍历

class Solution { 
public: 
    vector<int> postorderTraversal(TreeNode* root) { 
        vector<int>ans; 
        return morrisPostorder(root,ans); 
    } 
    vector<int> morrisPostorder(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==NULL) { 
                    mostRight->right=cur; 
                    cur=cur->left; 
                    continue; 
                } 
                else { 
                    mostRight->right=NULL; 
                    collect(cur->left,ans); 
                } 
            } 
            cur=cur->right; 
        } 
        collect(head,ans); 
        return ans; 
    } 
    void collect(TreeNode* head,vector<int>&ans) { 
        TreeNode* tail=reverse(head); 
        TreeNode* cur=tail; 
        while(cur!=NULL) { 
            ans.push_back(cur->val); 
            cur=cur->right; 
        } 
        reverse(tail); 
    } 
    TreeNode* reverse(TreeNode* cur) { 
        TreeNode* pre=NULL; 
        TreeNode* next=NULL; 
        while(cur!=NULL) { 
            next=cur->right; 
            cur->right=pre; 
            pre=cur; 
            cur=next; 
        } 
        return pre; 
    } 
};

后序遍历就是在 morris 遍历时，在第二次到达某个节点时，去逆序收集该节点左树的右边界，最后逆序收集整棵树的右边界。对于逆序操作，就类似于单链表的反转，记得最后需要反转回去。

5.Morris 遍历的局限性

很容易就能看出，局限性就是每个节点来到的次数比较少。因为 morris 遍历每个点最多来两次，而 dfs 每个点会来三次，所以一些需要 dfs 整合信息的情况 morris 就不适用了.

二、应用

1.验证二叉搜索树

class Solution { 
public: 
    bool isValidBST(TreeNode* root) { 
        TreeNode* cur=root; 
        TreeNode* mostRight=NULL; 
        TreeNode* pre=NULL; 
        bool ans=true; 
        while(cur!=NULL) { 
            mostRight=cur->left; 
            if(mostRight!=NULL) { 
                while(mostRight->right!=NULL&&mostRight->right!=cur) { 
                    mostRight=mostRight->right; 
                } 
                if(mostRight->right==NULL) { 
                    mostRight->right=cur; 
                    cur=cur->left; 
                    continue; 
                } 
                else { 
                    mostRight->right=NULL; 
                } 
            } 
            if(pre!=NULL&&pre->val>=cur->val) { 
                ans=false; 
            } 
            pre=cur; 
            cur=cur->right; 
        } 
        return ans; 
    } 
};

因为中序遍历时值单调递增就是 BST，所以直接中序遍历即可。所以多用一个 pre 变量记录上一个位置，然后每次比较即可。注意这里不能直接返回，需要都把那么改过的右指针改回来，最后再返回。

2.二叉树的最小深度

class Solution { 
public: 
    int minDepth(TreeNode* head) { 
        if(head==NULL) { 
            return 0; 
        } 
        TreeNode* cur=head; 
        TreeNode* mostRight=NULL; 
        int preLevel=0; 
        int rightLen=0; 
        int ans=1e9; 
        while(cur!=NULL) { 
            mostRight=cur->left; 
            if(mostRight!=NULL) { 
                rightLen=1; 
                while(mostRight->right!=NULL&&mostRight->right!=cur) { 
                    rightLen++; 
                    mostRight=mostRight->right; 
                } 
                if(mostRight->right==NULL) { 
                    preLevel++; 
                    mostRight->right=cur; 
                    cur=cur->left; 
                    continue; 
                } 
                else { 
                    if(mostRight->left==NULL) { 
                        ans=min(ans,preLevel); 
                    } 
                    preLevel-=rightLen; 
                    mostRight->right=NULL; 
                } 
            } 
            else { 
                preLevel++; 
            } 
            cur=cur->right; 
        } 
        rightLen=1; 
        cur=head; 
        while(cur->right!=NULL) { 
            rightLen++; 
            cur=cur->right; 
        } 
        if(cur->left==NULL) { 
            ans=min(ans,rightLen); 
        } 
        return ans; 
    } 
};

考虑再多设置两个变量，preLevel 表示上一个节点所在的层数，rightLen 为树右边界的长度，所以在找最右节点时可以求得 rightLen。之后，若是第一次来，因为之后 cur 要左移，所以 preLevel 直接加一。而如果是第二次来，那么如果此时的最右节点是叶节点，那么就可以直接统计 ans 了。否则，当前的层数就是左树最右节点的层数减去这个最右边界的长度。另外，如果压根没有左树，那么必然是从上方节点来的，所以 preLevel 直接加一即可。

注意，当遍历结束后，整棵树的最右节点是没有被统计过的，所以需要额外特判一下。

3.二叉树的最近公共祖先

class Solution { 
public: 
    TreeNode* lowestCommonAncestor(TreeNode* head, TreeNode* o1, TreeNode* o2) { 
        if(preOrder(o1->left,o1,o2)!=NULL||preOrder(o1->right,o1,o2)!=NULL) { 
            return o1; 
        } 
        if(preOrder(o2->left,o1,o2)!=NULL||preOrder(o2->right,o1,o2)!=NULL) { 
            return o2; 
        } 
        TreeNode* lleft=preOrder(head,o1,o2); 
        TreeNode* cur=head; 
        TreeNode* mostRight=NULL; 
        TreeNode* ans=NULL; 
        while(cur!=NULL) { 
            mostRight=cur->left; 
            if(mostRight!=NULL) { 
                while(mostRight->right!=NULL&&mostRight->right!=cur) { 
                    mostRight=mostRight->right; 
                } 
                if(mostRight->right==NULL) { 
                    mostRight->right=cur; 
                    cur=cur->left; 
                    continue; 
                } 
                else { 
                    mostRight->right=NULL; 
                    if(ans==NULL) { 
                        if(rightCheck(cur->left,lleft)) { 
                            if(preOrder(lleft->right,o1,o2)!=NULL) { 
                                ans=lleft; 
                            } 
                            lleft=cur; 
                        } 
                    } 
                } 
            } 
            cur=cur->right; 
        } 
        return ans!=NULL?ans:lleft; 
    } 
    TreeNode* preOrder(TreeNode* head,TreeNode* o1,TreeNode* o2) { 
        TreeNode* cur=head; 
        TreeNode* mostRight=NULL; 
        TreeNode* ans=NULL; 
        while(cur!=NULL) { 
            mostRight=cur->left; 
            if(mostRight!=NULL) { 
                while(mostRight->right!=NULL&&mostRight->right!=cur) { 
                    mostRight=mostRight->right; 
                } 
                if(mostRight->right==NULL) { 
                    if(ans==NULL&&(cur==o1||cur==o2)) { 
                        ans=cur; 
                    } 
                    mostRight->right=cur; 
                    cur=cur->left; 
                    continue; 
                } 
                else { 
                    mostRight->right=NULL; 
                } 
            } 
            else { 
                if(ans==NULL&&(cur==o1||cur==o2)) { 
                    ans=cur; 
                } 
            } 
            cur=cur->right; 
        } 
        return ans; 
    } 
    bool rightCheck(TreeNode* head, TreeNode* target) { 
        while(head!=NULL) { 
            if(head==target) { 
                return true; 
            } 
            head=head->right; 
        } 
        return false; 
    } 
};

感觉这个的思路和 tarjan 算法求 lca 很类似。

首先，定义 preOrder 方法为从某个节点开始，o1 和 o2 谁先被找到就返回谁，所以上来可以先特判两者是否其中一个是另一个的 lca。之后，再从 head 开始 preOrder 一遍，那么此时谁先被找到谁就是左侧的节点 left。

之后去跑 morris 遍历，当第二次来到当前节点时，去 check 看 left 是否在 cur 左树右边界上。如果在，那么就去看 left 的右树里是否有另一个。如果有，那么此时的 left 就是 lca。否则就把 left 设置为当前节点 cur。注意最后需要额外再考虑一下最后的 left。

大体的原理就是因为已经找到 left 了，所以就只用查右树即可。