快捷導(dǎo)航

Java 二叉樹遍歷特別篇之Morris遍歷

更新時間：2021年11月08日 10:14:30 作者：飛人01_01

二叉樹的遍歷（traversing binary tree）是指從根結(jié)點出發(fā)，按照某種次序依次訪問二叉樹中所有的結(jié)點，使得每個結(jié)點被訪問依次且僅被訪問一次。四種遍歷方式分別為：先序遍歷、中序遍歷、后序遍歷、層序遍歷

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

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

本期文章源碼：GitHub

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

一、Morris

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

觀察上面這顆二叉樹，腦補一下。當(dāng)我們一直往下遍歷時，走到值為4的節(jié)點，打印輸出4后，我該怎么回到2節(jié)點？每個節(jié)點都是只有指向左右孩子的引用，并沒有指向父節(jié)點的引用。

所以在遍歷4節(jié)點的時候，會提前將2節(jié)點的所有信息，放入棧里面，只有在4節(jié)點遍歷完成之后，才會彈出棧里的信息（2節(jié)點）。然后繼續(xù)遍歷其他的節(jié)點。

這也就是為什么遍歷二叉樹需要壓棧的原因。

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

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

前提：我們準(zhǔn)備兩個引用變量：cur和mostRight。 cur表示當(dāng)前遍歷的節(jié)點；mostRight表示cur節(jié)點左子樹中，往右邊遍歷，第一個沒有右孩子的節(jié)點。舉個例子：上圖中cur是1節(jié)點，則mostRight就是1節(jié)點左子樹中，往右下角遍歷，5節(jié)點就是第一個沒有右孩子的節(jié)點。

Morris遍歷細(xì)節(jié)：（cur初始化為根結(jié)點）

如果cur沒有左孩子，cur就向右孩子移動。（cur = cur.right）

如果cur有左孩子，那就找到cur左子樹中，最靠右的節(jié)點mostRight：

如果mostRight的右孩子是null，說明是第一次遍歷到mostRight。此時讓mostRight的右孩子指向cur。
如果mostRight的右孩子是cur，說明是第二次遍歷到mostRight。此時讓mostRight的右孩子等于null即可。

遍歷結(jié)束條件：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、循環(huán)找到mostRight節(jié)點
            2、判斷mustRight的右孩子是否為null
        }
        
        //mostRight等于null時
        cur = cur.right; //向右子樹移動
    }
}

上面的偽代碼就是大致的框架結(jié)構(gòu)，具體的代碼如下：

值得注意的是，當(dāng)?shù)谝淮伪闅v到mostRight時，讓mostRight的右孩子指向cur之后，cur 再往左子樹走，然后應(yīng)該再寫一句continue。讓代碼繼續(xù)往cur的左子樹繼續(xù)遍歷。

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

關(guān)于前序、中序、后序遍歷，都是在Morris的基礎(chǔ)之上，添加printf即可。具體的，請往下看。

二、前序遍歷

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

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

如果cur節(jié)點沒有左孩子，那就打印當(dāng)前cur的值
如果是第一次遍歷到mostRight節(jié)點，那就打印當(dāng)前cur的值

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

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

三、中序遍歷

前序遍歷順序：左頭右。

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

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

跟前序遍歷的區(qū)別只是mostRight這里，前序是第一次遍歷到mostRight就打印cur，中序是第二次遍歷到就打印。

當(dāng)然，這兩個printf可以提取出來，寫一行即可。這里只是為了讓大家清晰地認(rèn)識到中序遍歷。

四、后序遍歷（較難）

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

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

不急，我們來看一張圖：

不難發(fā)現(xiàn)，紅色的數(shù)值就是后序遍歷的結(jié)果。對比下左邊的二叉樹，紅色線條的指向，從左到右，從下到上的打印順序，竟然跟后序遍歷的結(jié)果是一樣的。

那我們就以這個為切入點，當(dāng)遍歷cur的時候，我們就可以打印cur左子樹的最靠右的那一排的節(jié)點。比如cur等于1節(jié)點的時候，我們就可以打印2、5節(jié)點。

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

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

逆序完成之后，打印輸出即可，然后在逆序回來，保持原來的狀態(tài)

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); //逆序回來，保持原狀態(tài)
}

上面兩個方法，就能實現(xiàn)打印行為。現(xiàn)在的問題是，怎么進行調(diào)用？？？

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

這里的后序遍歷，還是跟前序和中序差不多，只是打印函數(shù)，我們在第二次遍歷到mostRight調(diào)用即可。

比如：在上圖中，第二次遍歷到mostRight等于4節(jié)點時，我們就調(diào)用打印函數(shù)，傳遞的參數(shù)是cur的左孩子。再比如：第二次遍歷到mostRight等于5節(jié)點時，此時調(diào)用printList（cur.left），此時的cur是1節(jié)點。

看代碼更清晰：