快捷導(dǎo)航

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

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

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

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

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

本期文章源碼：GitHub

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

一、Morris

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

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

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

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

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

上圖橙色的線條，是Morris方法的作用，就是改變某些節(jié)點(diǎn)的右孩子引用。然后在具體的遍歷過(guò)程中，我們將橙色線條擦除即可。保證跟原二叉樹一模一樣。這就是Morris的思想。那么問(wèn)題來(lái)了，我們?cè)撊绾萎嬤@些橙色的線條呢？

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

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

如果cur沒(méi)有左孩子，cur就向右孩子移動(dòng)。（cur = cur.right）

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

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

遍歷結(jié)束條件：cur等于null時(shí)

偽代碼：

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é)點(diǎn)
            2、判斷mustRight的右孩子是否為null
        }
        
        //mostRight等于null時(shí)
        cur = cur.right; //向右子樹移動(dòng)
    }
}

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

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

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

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

二、前序遍歷

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

而Morris改前序遍歷，非常簡(jiǎn)單。記住兩個(gè)點(diǎn)，你就能獨(dú)自改前序遍歷。

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

就以上兩個(gè)點(diǎn)，添加到代碼里面即可。

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

三、中序遍歷

前序遍歷順序：左頭右。

中序跟前序的遍歷，這里很相似，也是記住兩個(gè)點(diǎn)即可：

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

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

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

四、后序遍歷（較難）

Morris改后序遍歷，稍微有一點(diǎn)點(diǎn)難，因?yàn)镸orris遍歷出來(lái)的左右結(jié)果，都滿足一個(gè)規(guī)律：當(dāng)前節(jié)點(diǎn)沒(méi)有左子樹，那么只會(huì)遍歷一次這個(gè)節(jié)點(diǎn)；當(dāng)前節(jié)點(diǎn)有左子樹，那么會(huì)有mostRight節(jié)點(diǎn)會(huì)返回到cur節(jié)點(diǎn)，也就是說(shuō)有左孩子的節(jié)點(diǎn)，會(huì)遍歷兩次。

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

不急，我們來(lái)看一張圖：

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

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

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

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

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

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

上面兩個(gè)方法，就能實(shí)現(xiàn)打印行為?，F(xiàn)在的問(wèn)題是，怎么進(jìn)行調(diào)用？？？

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

這里的后序遍歷，還是跟前序和中序差不多，只是打印函數(shù)，我們?cè)诘诙伪闅v到mostRight調(diào)用即可。

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

看代碼更清晰：

最后切記，當(dāng)24行~43行的循環(huán)結(jié)束后，還剩下整棵樹的最靠右的那一排節(jié)點(diǎn)沒(méi)有打印（對(duì)應(yīng)上圖就是：1、3、7節(jié)點(diǎn)還沒(méi)打?。?，要單獨(dú)調(diào)用打印函數(shù)，傳遞根結(jié)點(diǎn)即可。

好啦，以上全部就是Morris遍歷二叉樹的全部情況，牢牢抓住cur節(jié)點(diǎn)有沒(méi)有左子樹的情況，應(yīng)該就能很好理解了。