二叉樹的遍歷想必大家都不陌生，主要有三種遍歷方式：前序遍歷（pre-order traversal）驹碍，中序遍歷（in-order ~）還有后序遍歷（post-order ~）怀伦。所謂前中后脆烟，就是遍歷根節(jié)點相對于遍歷子樹的順序。這里假設讀者已經了解了最基礎的三種遍歷的定義房待，不再贅述邢羔。
這篇文章的目的就是用代碼實現(xiàn)二叉樹的遍歷驼抹。不僅要實現(xiàn)，還要多種方法實現(xiàn)张抄，還要讓讀者能記住一些寫法砂蔽。因為二叉樹遍歷應用實在很廣，是很基礎很實用的算法署惯，不得不熟悉左驾。
本篇文章編程語言為Kotlin（Python：？极谊？诡右？）。不熟悉這門語言的也沒關系轻猖，大致應該還是能看懂帆吻。
樹節(jié)點的定義：
class TreeNode(var value: Int = 0, var left: TreeNode? = null, var right: TreeNode? = null)
簡單的遞歸
二叉樹簡直就是為遞歸而生的。一棵二叉樹可以看成左子樹咙边，根節(jié)點和右子樹猜煮，也就是說往往可以對左右子樹遞歸調用。
對于遍歷败许，遞歸無疑是最簡單的解決方式王带。遞歸的思維是這樣的：假設遞歸函數(shù)的作用就是以某種方式遍歷樹，那么再來看左子樹市殷，根節(jié)點和右子樹愕撰，無非就是按照某個順序對左右子樹調用并把根節(jié)點放到結果里。
還是看代碼吧醋寝，真的很簡單（x?.let{}表示如果x不為null就執(zhí)行括號里面的內容搞挣，it在括號內指代x）：
// T:O(n) S:O(h)
fun inOrderRecur(root: TreeNode): List<Int> {
val ret = mutableListOf<Int>()
root.left?.let { ret.addAll(inOrderRecur(it)) }
ret.add(root.value)
root.right?.let { ret.addAll(inOrderRecur(it)) }
return ret
}
// T:O(n) S:O(h)
fun preOrderRecur(root: TreeNode): List<Int> {
val ret = mutableListOf<Int>()
ret.add(root.value)
root.left?.let { ret.addAll(preOrderRecur(it)) }
root.right?.let { ret.addAll(preOrderRecur(it)) }
return ret
}
// T:O(n) S:O(h)
fun postOrderRecur(root: TreeNode): List<Int> {
val ret = mutableListOf<Int>()
root.left?.let { ret.addAll(postOrderRecur(it)) }
root.right?.let { ret.addAll(postOrderRecur(it)) }
ret.add(root.value)
return ret
}
可以看到，遞歸代碼真的很短音羞，也非常好記憶囱桨。
不過遞歸畢竟是遞歸，這里也并沒有tail recursion嗅绰，效率總是不如迭代方法的舍肠。如何用非遞歸方法來實現(xiàn)遍歷呢？
模仿遞歸的棧解法
一個很科學的思路就是把遞歸“翻譯”成迭代办陷。既然我已經有了這么簡單方便的遞歸方法貌夕，我只需要把它們轉化成迭代方法，不就可以了嗎民镜？
那么這里的關鍵就是：如何“翻譯”啡专？
要模仿遞歸的思路，首先需要棧制圈，因為遞歸雖然沒有聲明棧们童，但是系統(tǒng)提供了棧畔况。
再仔細思考一下會發(fā)現(xiàn)節(jié)點的遍歷順序很重要，有些節(jié)點會留在之后再遍歷慧库。
有沒有一種類似于遞歸的棧解法跷跪，用很相似的代碼來實現(xiàn)三種遍歷？
有的齐板。訣竅就是引入一個表示是否已經遍歷過的布爾值isVisited吵瞻。遞歸其實也是有這么一個過程的，從第一次調用甘磨，到子問題橡羞，然后再回來。
節(jié)點第一次進棧時济舆，布爾值為false卿泽，之后再出現(xiàn)的時候，假設是true滋觉，那么添加到結果里签夭，否則改為true再按照遍歷順序進棧。
代碼如下：
// T:O(n) S:O(h)
fun inOrder(root: TreeNode): List<Int> {
val stk = Stack<Pair<TreeNode?, Boolean>>()
val ret = mutableListOf<Int>()
stk.push(Pair(root, false))
while (stk.isNotEmpty()) {
val p = stk.pop()
val cur = p.first
val isVisited = p.second
if (cur == null) {
continue
} else {
if (isVisited) {
ret.add(cur.value)
} else {
stk.push(Pair(cur.right, false))
stk.push(Pair(cur, true))
stk.push(Pair(cur.left, false))
}
}
}
return ret
}
// T:O(n) S:O(h)
fun preOrder(root: TreeNode): List<Int> {
val stk = Stack<Pair<TreeNode?, Boolean>>()
val ret = mutableListOf<Int>()
stk.push(Pair(root, false))
while (stk.isNotEmpty()) {
val p = stk.pop()
val cur = p.first
val isVisited = p.second
if (cur == null) {
continue
} else {
if (isVisited) {
ret.add(cur.value)
} else {
stk.push(Pair(cur.right, false))
stk.push(Pair(cur.left, false))
stk.push(Pair(cur, true))
}
}
}
return ret
}
// T:O(n) S:O(h)
fun postOrder(root: TreeNode): List<Int> {
val stk = Stack<Pair<TreeNode?, Boolean>>()
val ret = mutableListOf<Int>()
stk.push(Pair(root, false))
while (stk.isNotEmpty()) {
val p = stk.pop()
val cur = p.first
val isVisited = p.second
if (cur == null) {
continue
} else {
if (isVisited) {
ret.add(cur.value)
} else {
stk.push(Pair(cur, true))
stk.push(Pair(cur.right, false))
stk.push(Pair(cur.left, false))
}
}
}
return ret
}
這種解法代碼稍長一點椎侠，好在三種解法幾乎一模一樣第租，除了進棧的順序不同。這里進棧的順序就是對遍歷順序倒著來肺蔚，因為先進后出煌妈。
各顯神通的棧解法
另一種思路是拋棄遞歸的思路儡羔，而分別針對三種遞歸的特性來用棧實現(xiàn)遍歷宣羊。這樣一來，每種解法都顯得更加優(yōu)雅汰蜘，但是不同解法之間又不太一樣仇冯，至少像上面那樣只需要記一種解法是不可能的了。
代碼：
// T:O(n) S:O(h)
fun inOrderWithStack(root: TreeNode): List<Int> {
val stk = Stack<TreeNode>()
val ret = mutableListOf<Int>()
var cur: TreeNode? = root
while (cur != null || stk.isNotEmpty()) {
while (cur != null) {
stk.push(cur)
cur = cur.left
}
cur = stk.pop()
ret.add(cur.value)
cur = cur.right
}
return ret
}
// T:O(n) S:O(h)
fun preOrderWithStack(root: TreeNode): List<Int> {
val stk = Stack<TreeNode>()
val ret = mutableListOf<Int>()
stk.push(root)
while (stk.isNotEmpty()) {
val cur = stk.pop()
ret.add(cur.value)
cur.right?.let { stk.push(it) }
cur.left?.let { stk.push(it) }
}
return ret
}
// T:O(n) S:O(h)
fun postOrderWithDoubleStacks(root: TreeNode): List<Int> {
val stk1 = Stack<TreeNode>()
val stk2 = Stack<TreeNode>()
stk1.push(root)
while (stk1.isNotEmpty()) {
val cur = stk1.pop()
stk2.push(cur)
cur.left?.let { stk1.push(it) }
cur.right?.let { stk1.push(it) }
}
return stk2.map { it.value }.reversed()
}
三種解法雖然不同族操，但又有千絲萬縷的聯(lián)系苛坚。中序、前序都只需要一個棧色难，后序需要兩個棧泼舱，但后序和前序其實很相似。
挑戰(zhàn)：Morris遍歷
說到樹的遍歷枷莉，不提及Morris遍歷總是不完整的娇昙。
Morris遍歷能以O(n)的時間復雜度和O(1)的空間復雜度來實現(xiàn)三種遍歷，相對應的代價就是代碼更為復雜笤妙。
在實際面試中冒掌，除非明確要求噪裕，或者把握很大股毫，且又是瓶頸膳音，不然沒必要為了這O(n)的空間復雜度來用Morris，尤其是最復雜的后序遍歷铃诬。當然祭陷，做出解答之后也許可以提一下，說用Morris能得到更好的空間復雜度趣席。
既然是O(1)的空間復雜度颗胡，說明Morris算法不用棧，那么如何回到以前遍歷過的節(jié)點呢吩坝？
答案就是指針毒姨。
原本樹的葉子節(jié)點，左右兩個指針都是空的钉寝，Morris就在這方面“嘶∧牛花招”，讓其右指針指向遍歷順序該返回的節(jié)點嵌纲。
中序
以中序遍歷為例俘枫，考慮以下這棵樹：
1
/
3
/
4 2
/
5
遍歷的結果應該是54321，也就是說5的返回點是4逮走，4的返回點是3鸠蚪，2的返回點應該是1。
還是來看代碼吧：
// T:O(n) S:O(1)
fun inOrderMorris(root: TreeNode): List<Int> {
val ret = mutableListOf<Int>()
var cur: TreeNode? = root
while (cur != null) {
if (cur.left == null) {
ret.add(cur.value)
cur = cur.right
} else {
var node: TreeNode = cur.left!!
while (node.right != null && node.right != cur)
node = node.right!!
if (node.right == null) {
node.right = cur
cur = cur.left
} else {
ret.add(cur.value)
node.right = null
cur = cur.right
}
}
}
return ret
}
解釋一下這個代碼對于上面那棵樹的執(zhí)行過程：
- cur為1师溅，此時把2的右指針指向1茅信，cur往左走一步；
- cur為3墓臭，把4的右指針指向3蘸鲸，cur往左走一步；
- cur為4窿锉，把5的右指針指向4酌摇，cur往左走一步；
- cur為5嗡载，此時把5加入結果窑多，通過右指針返回4；
- cur為4洼滚，此時5的右指針還指向4埂息，說明4是第二次來了，把5的右指針復原，把4加入結果耿芹，cur往右走一步崭篡；
- cur為3，類似地把4的右指針復原吧秕，把3加入結果琉闪，cur往右走一步；
- cur為2砸彬，把2加入結果颠毙，通過右指針返回1；
- cur為1砂碉，把2的右指針復原蛀蜜，把1加入結果，往右走一步增蹭；
- cur為null滴某，結束
可以發(fā)現(xiàn)，Morris遍歷其實要走兩遍節(jié)點滋迈，第一遍主要是架設“后路”霎奢。
仔細思考，根節(jié)點左子樹的最右節(jié)點饼灿，不就是中序遍歷里面根節(jié)點的前一個元素嗎幕侠？因為是左子樹的最右節(jié)點，說明左子樹的中序已經完成碍彭，接下來就是返回根節(jié)點了晤硕。
第二遍就是獲得結果并復原指針。通過是否有“后路”來確定是不是第二遍庇忌，然后再做行動舞箍。
總而言之，非常巧妙漆枚。
Morris本人其實就提出了中序遍歷创译，其他人根據(jù)中序遍歷抵知，推出了前序和后序遍歷的Morris方法墙基。
前序
再來看看前序遍歷：
// T:O(n) S:O(1)
fun preOrderMorris(root: TreeNode): List<Int> {
val ret = mutableListOf<Int>()
var cur: TreeNode? = root
while (cur != null) {
if (cur.left == null) {
ret.add(cur.value)
cur = cur.right
} else {
var node = cur.left
while (node?.right != null && node.right != cur)
node = node.right
if (node?.right == null) {
ret.add(cur.value)
node?.right = cur
cur = cur.left
} else {
node.right = null
cur = cur.right
}
}
}
return ret
}
這個代碼明顯和中序非常像∷⑾玻總的來說残制，架設“后路”的思路還是一樣的，只不過加入結果的時機不同掖疮。
還是以上面那棵樹為例：
- cur為1初茶，先把1加入結果，再讓2指向1浊闪，cur往左走一步恼布；
- cur為3螺戳，把3加入結果，讓4指向3折汞，cur往左走一步倔幼；
- cur為4，把4加入結果爽待，讓5指向4损同，cur往左走一步；
- cur為5鸟款，把5加入結果膏燃，往右走一步，通過后路返回4何什；
- cur為4组哩，把5的后路復原，往右走一步处渣，通過后路返回3禁炒；
- cur為3，把4的后路復原霍比，往右走一步幕袱；
- cur為2，把2加入結果悠瞬，往右走一步们豌，通過后路返回1；
- cur為1浅妆，把2的后路復原，往右走一步凌外；
- cur為null，結束
可以看到康辑，中序和前序的行動軌跡是完全一樣的，而且都在最左端加入結果疮薇。區(qū)別在于胸墙，中序是回來的時候加入結果，前序是第一次就加入結果迟隅。
后序
Morris的后序又是另一個故事了，比前序和中序都要復雜很多智袭。
// T:O(n) S:O(1)
fun postOrderMorris(root: TreeNode): List<Int> {
val dummy = TreeNode()
dummy.left = root
val ret = mutableListOf<Int>()
var cur: TreeNode? = dummy
while (cur != null) {
if (cur.left == null) {
cur = cur.right
} else {
var node = cur.left
while (node?.right != null && node.right != cur)
node = node.right
if (node?.right == null) {
node?.right = cur
cur = cur.left
} else {
ret.addAll(traceBack(cur.left!!, node))
node.right = null
cur = cur.right
}
}
}
return ret
}
fun traceBack(from: TreeNode, to: TreeNode): List<Int> {
val ret = mutableListOf<Int>()
var cur: TreeNode = from
while (cur !== to) {
ret.add(cur.value)
cur = cur.right!!
}
ret.add(to.value)
return ret.reversed()
}
試推演執(zhí)行步驟如下：
- cur為dummy奔缠，將1的右指針指向dummy，cur往左走一步吼野；
- cur為1添坊，將2的右指針指向1箫锤，cur往左走一步；
- cur為3谚攒，將4的右指針指向3，cur往左走一步馏臭；
- cur為4，將5的右指針指向4绕沈，cur往左走一步；
- cur為5乍狐，此時直接通過后路返回4；
- cur為4浅蚪，將5加入結果烫罩，并復原5的右指針惜傲，通過后路返回3贝攒；
- cur為3，類似地將4加入結果隘弊，復原4的右指針，向右走一步嚣鄙；
- cur為2，通過后路返回1；
- cur為1，將2卧蜓、3加入結果把敞，復原2的右指針弥奸，向右走一步；
- cur為dummy奋早，將1加入結果盛霎，復原1的右指針，向右走一步耽装；
- cur為null，結束
架設路徑仍舊是老套路规个，只是這次不僅使用了一個dummy node姓建，而且還需要一個子函數(shù)來配合獲取結果，確實復雜了很多速兔。
