大家好~我叫「小鹿鹿鹿」，是本賣萌小屋的第二位簽約作（萌）者（貨）。和小夕一樣現在在從事NLP相關工作，希望和大家分享NLP相關的、不限于NLP的各種小想法，新技術。這是我的第一篇試水文章，初來乍到，希望大噶多多滋辭(●'?'●)。

冬天已經來了，秋招早已悄無聲息的結束。作為一個已經工作了兩年的老人，校招面試感覺就像高考一樣遙遠。但是呢，雖然工作了，還是要時刻保持危機感的呀，萬一哪天就要跳槽了呢(￣?￣)。

遙想當年面試的時候，由于沒有學過數據結構，在面試官出算法題之前就老實交待家底：“我的算法和數據結構不太行，樹呀圖呀都不太會(????)"。但是經過兩年斷斷續續的學習，發現其實樹是一個套路非常明顯的一類算法題，而遍歷樹是解決絕大多數樹問題的基礎（很多題目都是在樹的遍歷上擴展），下面小鹿就以樹的遍歷為例，解剖樹里面深深的套路吧o(*￣▽￣*)o。

?

樹的基礎回顧

---

二叉樹長什么樣子，小鹿這里就不上圖啦，所謂的根節點、葉子節點也不介紹啦。我們知道，二叉樹的遍歷分為三種：前序、中序和后序。這三種序的不同主要就是在于什么時候訪問根節點。以前序為例，在遍歷一顆樹的時候先訪問根節點，再遍歷其根節點的左子樹，最后訪問根節點的右子樹。而中序遍歷就是先遍歷左子樹，再訪問根節點，最后遍歷右子樹；后序遍歷小鹿就不重復啦。

樹的遞歸

---

樹有一個很好的特性，就是一棵樹的根節點的左右子樹仍然是一顆樹

這好像是一句正確的廢話╮(￣▽￣"")╭

所以我們可以把一棵復雜的大樹，分解成兩顆稍微小一點的樹，依次類推，最后變成最小的單元（只有一個節點的樹）。不管怎么講，處理只有一個節點的樹是不是超級容易！！！這個呢就是遞歸的思想，所以說到這里，我們以后只要遇到關于樹的問題，誰還不會用遞歸走一波呢！

下面就來開始實踐！用遞歸的思想實現二叉樹的前序、中序、后序遍歷（遍歷結果記錄在self.ans的向量里）。小鹿這里就用python寫啦（真的不要糾結編程語言噢）。遍歷一個有n個節點的樹，其時間復雜度和空間復雜度都是O(n)。

class Solution(object):def __init__(self):self.ans = []def preorderRecursive(self, root):if root:self.ans.append(root.val)self.preorderRecursive(root.left)self.perorderRecursive(root.right)def inorderRecursive(self, root):if root:self.inorderRecursive(root.left)self.ans.append(root.val)self.inorderRecursive(root.right)def postorderRecursive(self, root):if root:self.postorderRecursive(root.left)self.postorderRecursive(root.right)self.ans.append(root.val)

樹和棧

---

用遞歸的思路解決樹的遍歷或者其他樹的問題，思路非常清晰，代碼也會非常的簡單清楚。當我們在使用遞歸（函數的嵌套）的時候，其本質是在調用棧。我們可以用棧來實現樹的遍歷，進一步理解遞歸的思想。

class Solution(object):def __init__(self):self.ans = []def preorderStack(self, root):aStack = []if root:aStack.append(root)while aStack:p = aStack.pop()self.ans.append(p.val)if p.right:aStack.append(p.right)if p.left:aStack.append(p.left)return self.ansdef inorderStack(self, root):stack = []p = rootwhile p:stack.append(p)p = p.leftwhile stack:p = stack.pop()self.ans.append(p.val)p = p.rightwhile p:stack.append(p)p = p.leftreturn self.ansdef postorderStack(self, root)aStack = []prev = Nonep = rootwhile aStack or p:if p:aStack.append(p)p = p.leftelse:p = aStack[-1]if p.right == prev or p.right is None:self.ans.append(p.val)prev = paStack.pop()p = Noneelse:p = p.right return self.ans

用棧來實現樹的遍歷就稍微復雜一點啦。首先前序是最簡單的，我們用一個棧（first-in-last-out）來維護樹遍歷的順序。初始狀態是把非空的根節點push到棧中，逐個從棧中取出節點，訪問其值，然后先push右節點再push左節點到棧中，就保證訪問順序是?root->left->right?啦。超級簡單有木有！

中序遍歷就稍微難一些了，在訪問一個節點之前需要訪問其 left-most?節點，將其左節點逐個加入到棧中，直到當前節點為None。然后從棧中取出節點，由于棧的特性，在取出某個節點之前，其左節點已經被訪問，所以就可以安心的訪問該節點，然后把當前節點置為其右節點，依次類推。

后序遍歷和中序遍歷差不多，在中序遍歷的基礎上需要增加一個prev記錄上一個訪問的節點，確認在訪問某個節點之前其右節點是否已經被訪問。

用棧的方式遍歷樹，更加顯式的告訴了大家樹遍歷的時候是怎么回溯的，其時間空間復雜度仍然是O(n)。

Morris遍歷

---

下面小鹿要給大家介紹一個神級樹遍歷方法Morris，使其空間復雜度從O(n)變成O(1)!

樹的遍歷一個難點就是確定什么時候以及回溯如何回溯（好像是兩個點），第一種遞歸的方法通過函數的嵌套實現回溯，第二種方法通過棧存儲節點的順序實現回溯，而Morris則是利用樹中空節點記錄每個節點其回溯的節點，實現空間復雜度為O(1)的遍歷。

具體來說，當我們訪問了某個左子樹最右的節點后需要回溯到其左子樹的根節點，但是怎么回去呢，我們需要在之前加一個鏈接，將該根節點連到其左子樹的最右節點的右節點上。是不是有點繞呢(╯﹏╰)b，不慌！小鹿帶你一起做一遍中序遍歷的例子就清楚啦~~

以上面的圖為例做中序遍歷，當前節點為6（curr=6）時，找到其左子樹的最右節點5，添加鏈接備用，這樣從節點5我們就可以回溯到節點6。更新當前節點，curr=2，重復相同的操作。當curr=1時，到達葉子節點，輸出(節點變藍)，因為之前添加了鏈接，所以可以從節點1回溯到節點2，回溯刪除鏈接。當前節點變成4，以此類推下去

已經懵逼的小伙伴們請仔細品味下面的代碼(￣▽￣)～

class Solution(object):def __init__(self):self.ans = []def inorderMorris(self, root):p = rootwhile p:if p.left is None:#left-most nodeself.ans.append(p.val)p = p.rightelse:#find prev, the right-most node of the left treeprev = p.leftwhile prev.right and prev.right != p:prev = prev.rightif prev.right is None:#first time to visit pprev.right = p #add linkp = p.leftelse:#second time to visit pself.ans.append(p.val)prev.right = Nonep = p.rightreturn self.ansdef preorderMorris(self, root):p = rootprev = Nonewhile p:if p.left is None:#left-most nodeself.ans.append(p.val)p = p.rightelse:#find right-most node of the left treeprev = p.leftwhile prev.right and prev.right != p:prev = prev.rightif prev.right is None:#first time to visit pprev.right = p #add linkself.ans.append(p.val)p = p.leftelse:#second time to visit pp = p.right #back to rootprev.right?=?None?#delete?the?linkreturn?self.ans??????????????????

Morris前序遍歷和中序遍歷幾乎一模一樣，唯一的差別就是在第一次訪問節點的時候就輸出，還是第二次訪問節點的時候輸出。Morris后序遍歷在此基礎上還要稍微的復雜一丟丟。因為后續遍歷根節點最后輸出，需要增加一個dump節點作為假的根節點，使其的左子樹的 right-most 指向原來的根節點。話不多說，我們來看下代碼吧！

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution(object):def __init__(self):self.ans = []def postorderMorris(self, root):dump = TreeNode(0)dump.left = rootp = dumpwhile p:if p.left is None:p = p.rightelse:prev = p.leftwhile prev.right and prev.right != p:prev = prev.rightif prev.right is None:#first time to visit pprev.right = pp = p.leftelse:#second time to visit pself.singleLinkReverseTraversal(p.left, prev)prev.right = Nonep = p.rightreturn self.ansdef singleLinkReverseTraversal(self, start, end):#take the right branch from start to end as single link#travel reverselyif start == end:self.ans.append(start.val)returnself.reverse(start, end)curr = endwhile curr != start:self.ans.append(curr.val)curr = curr.rightself.ans.append(curr.val)self.reverse(end, start)def reverse(self, start, end):if start == end:returnprev = Nonecurr = startwhile curr != end:tmp = curr.rightcurr.right = prevprev = currcurr = tmpcurr.right = prev

眼尖的小伙伴看了代碼之后就會發現，Morris后序遍歷怎么多了兩個函數，怎么和前序和中序不一樣了呢ヽ(`Д′)ﾉ！這個Morris后序遍歷確實比較挺難理解，我們還是用最簡單的圖示來走一遍代碼的意思吧~~~

開始除了加了一個dump節點以外，都是一樣的一路向下，到達left-most節點3，不輸出（注意啦！不一樣啦！）然后回溯到節點2，逆序輸出從3到3的節點，刪除鏈接。從節點2一路往右回溯到節點1，逆序輸出從其左節點2到prev節點6，刪除節點。以此類推，就噢啦ヽ(￣▽￣)ﾉ。

? ? ??

現在大家都清楚了吧~~不清楚的地方歡迎在評論區提出噢，小鹿會盡最大努力為大家答疑解惑嗒(￣▽￣)／后面小鹿鹿鹿還會持續推送關于算法和數據結構的小文章，大家有興趣的話歡迎關注訂閱哦(′▽`)ﾉ?。

感謝大家的閱讀[]~(￣▽￣)~*（鞠躬）

總結

以上是生活随笔為你收集整理的算法与数据结构--空间复杂度O(1)遍历树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。