在前面，我們簡單提及過二叉樹的遍歷方式，有遞回和非遞回兩個版本的遍歷，仔細想一想，不管是遞回的，還是非遞回的遍歷，兩種版本的遍歷都是需要耗費大量的、額外的空間，比如當我們二叉樹的高度有100層，那么遞回時，系統就會一直壓堆疊，最壞情況下，一直要壓入100次遍歷的遞回函式，因為此處的空間復雜度是跟這顆二叉樹的高度相關的，所以有人就在想，有沒有什么方式，能夠使這個空間復雜度再壓縮一點呢？

前期文章：二叉樹的非遞回遍歷

本期文章原始碼：GitHub

有，肯定是有的，那就是今天的主題：Morris遍歷，這種思想就能使二叉樹的遍歷，空間復雜度為O(1)，那我們直接開始吧！

一、Morris

在講解之前，我們來分析一下，為什么遍歷二叉樹需要壓堆疊？

觀察上面這顆二叉樹，腦補一下，當我們一直往下遍歷時，走到值為4的節點，列印輸出4后，我該怎么回到2節點？ 每個節點都是只有指向左右孩子的參考，并沒有指向父節點的參考，

所以在遍歷4節點的時候，會提前將2節點的所有資訊，放入堆疊里面，只有在4節點遍歷完成之后，才會彈出堆疊里的資訊（2節點），然后繼續遍歷其他的節點，

這也就是為什么遍歷二叉樹需要壓堆疊的原因，

那么我們就在想啊，有沒有種方法，能夠不壓堆疊，就能從4節點直接回傳到2節點呢？ 那就是利用4節點的右孩子參考，因為4節點是葉子節點，沒有左右孩子節點的， 我們將4節點的右孩子參考，指向2節點，這樣就能夠從4節點直接回傳到2節點了，具體的圖片如下：

上圖橙色的線條，是Morris方法的作用，就是改變某些節點的右孩子參考，然后在具體的遍歷程序中，我們將橙色線條擦除即可，保證跟原二叉樹一模一樣，這就是Morris的思想， 那么問題來了，我們該如何畫這些橙色的線條呢？

前提：我們準備兩個參考變數：cur和mostRight， cur表示當前遍歷的節點；mostRight表示cur節點左子樹中，往右邊遍歷，第一個沒有右孩子的節點，舉個例子：上圖中cur是1節點，則mostRight就是1節點左子樹中，往右下角遍歷，5節點就是第一個沒有右孩子的節點，

Morris遍歷細節：（cur初始化為根結點）

• 如果cur沒有左孩子，cur就向右孩子移動，（cur = cur.right）
• 如果cur有左孩子，那就找到cur左子樹中，最靠右的節點mostRight：
  • 如果mostRight的右孩子是null，說明是第一次遍歷到mostRight，此時讓mostRight的右孩子指向cur，
  • 如果mostRight的右孩子是cur，說明是第二次遍歷到mostRight，此時讓mostRight的右孩子等于null即可，
• 遍歷結束條件：cur等于null時

偽代碼：

public void morris(Node root) {
    if (root == null) {
        return;
    }
    
    Node cur = root;
    Node mostRight = null;
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight 不等于null) {
        	1、回圈找到mostRight節點
            2、判斷mustRight的右孩子是否為null
        }
        
        //mostRight等于null時
        cur = cur.right; //向右子樹移動
    }
}

上面的偽代碼就是大致的框架結構，具體的代碼如下：

值得注意的是，當第一次遍歷到mostRight時，讓mostRight的右孩子指向cur之后，cur 再往左子樹走，然后應該再寫一句continue，讓代碼繼續往cur的左子樹繼續遍歷，

可能有的同學分不清，什么時候是第一次遍歷到mostRight，什么是第二次遍歷到mostRight，簡單點說，第一次就是mostRight的右孩子是null時，此時我們需要將右孩子指向cur；第二次是mostRight的右孩子指向cur的時候，此時我們需要將右孩子重新改回來，改為null，

關于前序、中序、后序遍歷，都是在Morris的基礎之上，添加printf即可，具體的，請往下看，

二、前序遍歷

我們都知道前序遍歷的順序是：頭左右，

而Morris改前序遍歷，非常簡單，記住兩個點，你就能獨自改前序遍歷，

• 如果cur節點沒有左孩子，那就列印當前cur的值
• 如果是第一次遍歷到mostRight節點，那就列印當前cur的值

就以上兩個點，添加到代碼里面即可，

其他的代碼，原封不動，只添加這兩句代碼即可完成前序遍歷，

三、中序遍歷

前序遍歷順序：左頭右，

中序跟前序的遍歷，這里很相似，也是記住兩個點即可：

• 如果cur沒有左孩子，直接列印輸出cur的值
• 如果mostRight是第二次遍歷到，那就列印輸出cur的值

跟前序遍歷的區別只是mostRight這里，前序是第一次遍歷到mostRight就列印cur，中序是第二次遍歷到就列印，

當然，這兩個printf可以提取出來，寫一行即可，這里只是為了讓大家清晰地認識到中序遍歷，

四、后序遍歷（較難）

Morris改后序遍歷，稍微有一點點難，因為Morris遍歷出來的左右結果，都滿足一個規律：當前節點沒有左子樹，那么只會遍歷一次這個節點；當前節點有左子樹，那么會有mostRight節點會回傳到cur節點，也就是說有左孩子的節點，會遍歷兩次，

后序遍歷是每個節點，遍歷到第3次的時候，才列印輸出，現在可好，Morris遍歷最多只能遍歷到2次，那該如何是好？？？

不急，我們來看一張圖：

不難發現，紅色的數值就是后序遍歷的結果，對比下左邊的二叉樹，紅色線條的指向，從左到右，從下到上的列印順序，竟然跟后序遍歷的結果是一樣的，

那我們就以這個為切入點，當遍歷cur的時候，我們就可以列印cur左子樹的最靠右的那一排的節點，比如cur等于1節點的時候，我們就可以列印2、5節點，

要滿足從下到上的列印順序，最容易想到的就是搞一個堆疊，壓堆疊進行，然后再依次彈出堆疊并列印，這樣的話，空間復雜度就不是O(1)了， 大家是否還記得逆序單鏈表？我們將那一排的節點，進行逆序，然后列印輸出之后，再逆序回來即可，

//逆序那一排節點
public Node reverseList(Node node) {
    Node pre = null;
    Node next = null;
    while (node != null) {
        next = node.right; //逆序右子樹那一排節點
        node.right = pre;
        pre = node;
        node = next;
    }
    return pre;
}

逆序完成之后，列印輸出即可，然后在逆序回來，保持原來的狀態

public void printList(Node node) {
    Node newHead = reverseList(node); //逆序
    node = newHead; //先保存newHead，等會逆序
    
    while (newHead != null) {
        System.out.print(newHead.val + " ");
        newHead = newHead.right; //向右子樹走
    }
    reverseList(node); //逆序回來，保持原狀態
}

上面兩個方法，就能實作列印行為，現在的問題是，怎么進行呼叫？？？

Morris遍歷，有的節點會遍歷到一次，而有的節點會遍歷到兩次，牢牢抓住這兩種情況，Morris遍歷就簡單了，

這里的后序遍歷，還是跟前序和中序差不多，只是列印函式，我們在第二次遍歷到mostRight呼叫即可，

比如：在上圖中，第二次遍歷到mostRight等于4節點時，我們就呼叫列印函式，傳遞的引數是cur的左孩子，再比如：第二次遍歷到mostRight等于5節點時，此時呼叫printList（cur.left），此時的cur是1節點，

看代碼更清晰：

最后切記，當24行~43行的回圈結束后，還剩下整棵樹的最靠右的那一排節點沒有列印（對應上圖就是：1、3、7節點還沒列印），要單獨呼叫列印函式，傳遞根結點即可，

好啦，以上全部就是Morris遍歷二叉樹的全部情況，牢牢抓住cur節點有沒有左子樹的情況，應該就能很好理解了，