開心一刻
一天，有個粉絲遇到感情方面的問題，找我出出主意
粉絲：我女朋友吧，就是先天有點病，聽不到人說話，也說不了話，現在我家里人又給我介紹了一個，我該怎么辦
我：這個問題很難去解釋，我覺得一個人活著，他要對身邊的人負責，對家人負責，對自己負責
從語音中我能感受得到粉絲很難受，我繼續補充
我：我不是說讓你放棄掉你的女朋友，你們一定是有一定的感情基礎才在一起的，但你還是需要衡量衡量你的未來
我能明顯感覺到粉絲已經在抽泣，繼續說道
我：當然，這個時候離開肯定是不合適的，對吧？
粉絲：是的
我：這種感情的問題，我很難說讓你怎么樣，這個只有你自己去衡量，找到一個最合適的解決辦法
粉絲哭泣到：我真的不知道怎么辦
我最不忍心看別人哭，安慰道：你先別哭，問題總有辦法解決的，哭不是解決問題的辦法，你先平復下
過了一會，粉絲說道：我知道了，我還是遵從家里的意見吧，給我現在的女朋友氣放了
我：女朋友氣... 我放你個大烏龜
前情回顧
二叉樹的遍歷 → 不用遞回，還能遍歷嗎中講到了二叉樹的深度遍歷的實作方式：遞回、堆疊+迭代
不管采用何種方式，額外空間復雜度都是 O(N)
那有沒有額外空間復雜度 O(1) 的遍歷方式了？
很早之前就被人給專研出來了，也就是本文的主角：Morris Traversal
Morris Traversal
因為它由 Joseph Morris 發明的，所以叫 Morris Traversal
遞回、堆疊+迭代的遍歷，本質都是使用了堆疊結構進行輔助，所以在處理完某個節點后能回到上層去
二叉樹的結構決定了它從上層到下層（根到葉子）很容易，但從下層到上層卻很難，因為只有父節點指向子節點的指標，而沒有子節點指向父節點的指標
Morris 遍歷的實質就是避免使用堆疊結構，而是讓下層到上層有指標，通過底層節點指向 null 的空閑指標指向上層的某個節點，從而實作下層到上層的移動
空閑指標從哪來？二叉樹的葉子節點，或者只有單個孩子的節點（左指標空閑或右指標空閑）
具體實作，我們往下看
移動規則
也就是遍歷程序；設當前節點為 cur ，初始 cur = root ，則 cur 的移動規則如下
1、如果 cur 沒有左子樹，則讓 cur 向右移動，即 cur = cur.right
2、如果 cur 有左子樹，則找到 cur 左子樹最右的節點，記作 mostRight
2.1、如果 mostRight 的右指標指向 null ，讓其指向 cur ，然后 cur 向左移動
2.2、如果 mostRight 的右指標指向 cur ，讓其指向 null ，然后 cur 向右移動
3、當 cur 為 null 時，遍歷停止
這描述還是有點抽象，我們結合具體的二叉樹，利用移動規則把二叉樹遍歷一遍
初始二叉樹如下
1）初始 cur 在節點 a，此時 cur 有左子樹，找到其左子樹的最右節點，即節點 k，k 的右指標指向 null ，讓其指向 cur ，然后 cur 左移
此時二叉樹結構如下， cur 第一次來到節點 b
2）此時 cur 在節點 b， cur 有左子樹，找到其左子樹的最右節點，即節點 d，d 的右指標指向 null ，讓其指向 cur ，然后 cur 左移
此時二叉樹結構如下， cur 第一次來到節點 d
3）此時 cur 在節點 d，cur 沒有左子樹， cur 右移
此時二叉樹結構如下， cur 第二次來到節點 b
4）此時 cur 在節點 b， cur 有左子樹，找到其左子樹的最右節點，即節點 d，d 的右指標指向 cur ，讓其指向 null ，然后 cur 右移
此時二叉樹結構如下， cur 第一次來到節點 e
這里大家可能會有疑問：找 cur 的左子樹的最右節點時，找到的不應該是節點 c 嗎？
所以這里有細節要處理，找左子樹最右節點的時候，遇到兩種情況（右指標指向 null 或右指標指向 cur ）都需要停止尋找，用代碼描述就是：
5）此時 cur 在節點 e， cur 有左子樹，找到其左子樹的最右節點，即節點 h，h 的右指標指向 null ，讓其指向 cur ，然后 cur 左移
此時二叉樹結構如下， cur 第一次來到節點 h
6）此時 cur 在節點 h， cur 沒有左子樹， cur 右移
此時二叉樹結構如下， cur 第二次來到節點 e
7）此時 cur 在節點 e， cur 有左子樹，找到其左子樹的最右節點，即節點 h，h 的右指標指向 cur ，讓其指向 null ，然后 cur 右移
此時二叉樹結構如下， cur 第一次來到節點 k
8）此時 cur 在節點 k， cur 沒有左子樹， cur 右移
此時二叉樹結構如下， cur 第二次來到節點 a（為什么是第二次？因為最初從 a 開始的）
9）此時 cur 在節點 a， cur 有左子樹，找到其左子樹的最右節點，即節點 k，k 的右指標指向 cur ，讓其指向 null ，然后 cur 右移
此時二叉樹結構如下， cur 第一次來到節點 c
10）此時 cur 在節點 c， cur 有左子樹，找到其左子樹的最右節點，即節點 g，g 的右指標指向 null ，讓其指向 cur ，然后 cur 左移
此時二叉樹結構如下， cur 第一次來到節點 f
11）此時 cur 在節點 f， cur 沒有左子樹， cur 右移
此時二叉樹結構如下， cur 第一次來到節點 g
12）此時 cur 在節點 g， cur 沒有左子樹， cur 右移
此時二叉樹結構如下， cur 第二次來到節點 c
13）此時 cur 在節點 c， cur 有左子樹，找到其左子樹的最右節點，即節點 g，g 的右指標指向 cur ，讓其指向 null ， cur 右移
此時二叉樹結構如下， cur = null
14）此時 cur 為 null ，遍歷停止
可以看到，二叉樹回到了最初的狀態，最終結構與最初一致
前面步驟有點長，看的可能不夠直觀，我們來看個完整版的
上述的遍歷就是 Morris Traversal ， cur 所經歷的節點 a -> b -> d -> b -> e -> h -> e -> k -> a -> c -> f -> g -> c 組成了 Morris 序
在遍歷的程序中，相信大家已經得出一個規律：有左子樹的節點（b、e、a、c）會到達兩次，沒有左子樹的節點（d、h、k、f、g）則只會到達一次
這絕對不是巧合啊！這是 Morris Traversal 移動規所產生的必然結果
對于那些能達到兩次的節點，我們如何區分是第一次到達，還是第二次到達？
在上述的遍歷程序中，相信大家已經找到答案了
1、如果其左子樹的最右節點指向 null ，即 mostRight.right = null ，則該節點是第一次到達
2、如果其左子樹的最右節點指向自身，即 mostRight.right = cur ，則該節點是第二次到達
經過了上述諸多的準備， Morris Traversal 代碼實作就非常簡單了
代碼實作
相信大家都能看懂這個代碼，沒看懂的再去把前面的遍歷程序再看看
Morris Traversal 一定要看懂，不然后面的深度遍歷就玩不動了
先序遍歷
我們對比下 先序序列 和 Morris 序列
發現了什么？ Morris Traversal 第二次到達的節點不列印，就是 先序序列 了
代碼也就手到擒來了
中序遍歷
我們對比下 中序序列 和 Morris 序列
只會遍歷一次的節點，直接列印；會遍歷兩次的節點，第一次的時候不列印，第二次列印，就得到了 中序序列
代碼很容易擼出來了
后序遍歷
對比 后序序列 和 Morris 序列
一眼看不出有什么關系
通過 Morris Traversal 得到 后續序列 確實不容易想到，我們直接看前輩們的經驗
被遍歷到兩次的節點的先后順序：b、e、a、c
1、b 節點的左子樹的右邊界：d，逆序列印它還是 d
2、e 節點的左子樹的右邊界：h，逆序列印它還是 h
3、a 節點的左子樹的右邊界：b -> e -> k，逆序列印就是：k -> e -> b
4、c 節點的左子樹的右邊界：f -> g，逆序列印就是：g -> f
5、整棵樹的右邊界：a -> c，逆序列印就是：c -> a
把逆序列串起來：d -> h -> k -> e -> b -> g -> f -> c -> a，這就是 后序序列
問題又來了，如何逆序列印右邊界，并且額外空間復雜度 O(1) ；其實就是單向鏈表的逆序輸出，不知道的可以查看：單向鏈表的花式玩法 → 還在玩反轉？
我們來看代碼
總結
額外空間復雜度
只用到了有限幾個變數， Morris Traversal 額外空間復雜度 O(1)
時間復雜度
Morris Traversal 時間復雜度是不是 O(N) ？
我們先看個極端的案例
它的時間復雜度是 2 * O(N)，這個沒什么問題吧？
常數項可以拿掉，所以時間復雜度是 O(N)
注意點
Morris Traversal 遍歷程序中會改變二叉樹的結構，在一些并發的場景需要慎重使用
參考
《程式員代碼面試指南：IT 名企演算法與資料結構題目最優解》
Morris遍歷圖解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/413034.html
標籤：其他
上一篇：編程進階之路，雖無捷徑但有長短