我們之前說了二叉樹基礎及二叉的幾種遍歷方式及練習題，今天我們來看一下二叉樹的前序遍歷非遞歸實現。

前序遍歷的順序是， 對于樹中的某節點，先遍歷該節點，然后再遍歷其左子樹，最后遍歷其右子樹。

我們先來通過下面這個動畫復習一下二叉樹的前序遍歷。

迭代遍歷

我們試想一下，之前我們借助隊列幫我們實現二叉樹的層序遍歷，

那么可不可以，也借助數據結構，幫助我們實現二叉樹的前序遍歷。

假設我們的二叉樹為 ［1，2，3］。我們需要對其進行前序遍歷。其遍歷順序為

當前節點 1，左孩子 2，右孩子 3。

這里可不可以用棧，幫我們完成前序遍歷呢？

棧和隊列的那些事

我們都知道棧的特性是先進后出，我們借助棧來幫助我們完成前序遍歷的時候。

則需要注意的一點是，我們應該先將右子節點入棧，再將左子節點入棧。

這樣出棧時，則會先出左節點，再出右子節點，則能夠完成樹的前序遍歷。

我們用一句話對上圖進行總結，當棧不為空時，棧頂元素出棧，如果其右孩子不為空，則右孩子入棧，其左孩子不為空，則左孩子入棧。還有一點需要注意的是，我們和層序遍歷一樣，需要先將 root 節點進行入棧，然后再執行 while 循環。

看到這里你已經能夠自己編寫出代碼了，不信你去試試。

時間復雜度：O（n） 需要對所有節點遍歷一次

空間復雜度：O（n） 棧的開銷，平均為 O（logn） 最快情況，即斜二叉樹時為 O（n）

參考代碼

class Solution {

public List《Integer》 preorderTraversal（TreeNode root） {

List《Integer》 list = new ArrayList《》（）;

Stack《TreeNode》 stack = new Stack《》（）;

if （root == null） return list;

stack.push（root）;

while （！stack.isEmpty（）） {

TreeNode temp = stack.pop（）;

if （temp.right ！= null） {

stack.push（temp.right）;

}

if （temp.left ！= null） {

stack.push（temp.left）;

}

//這里也可以放到前面

list.add（temp.val）;

}

return list;

}

}

Morris

Morris 遍歷利用樹的左右孩子為空（大量空閑指針），實現空間開銷的極限縮減。這個遍歷方式，稍微有那么一丟丟難理解，不過結合動圖，也就一目了然，下面我們先看動畫吧。

看完視頻，是不是感覺自己搞懂了，又感覺自己沒搞懂，哈哈，咱們繼續往下看。

我們之前說的，Morris 遍歷利用了樹中大量空閑指針的特性，我們需要找到當前節點的左子樹中的最右邊的葉子節點，將該葉子節點的 right 指向當前節點。例如當前節點為2，其左子樹中的最右節點為 9 ，則在 9 節點添加一個 right 指針指向 2。

其實上圖中的 Morris 遍歷遵循兩個原則，我們在動畫中也能夠得出。

1.當 p1.left == null 時，p1 = p1.right。（這也就是我們為什么要給葉子節點添加 right 指針的原因）

2.如果 p1.left ！= null，找到 p1 左子樹上最右的節點。（也就是我們的 p2 最后停留的位置），此時我們又可以分為兩種情況，一種是葉子節點添加 right 指針的情況，一種是去除葉子節點 right 指針的情況。

如果 p2 的 right 指針指向空，讓其指向 p1，p1向左移動，即 p1 = p1.left

如果 p2 的 right 指針指向 p1，讓其指向空，（為了防止重復執行，則需要去掉 right 指針）p1 向右移動，p1 = p1.right。

這時你可以結合咱們剛才提到的兩個原則，再去看一遍動畫，并代入規則進行模擬，差不多就能完全搞懂啦。

下面我們來對動畫中的內容進行拆解 ，

首先 p1 指向 root節點

p2 = p1.left，下面我們需要通過 p2 找到 p1的左子樹中的最右節點。即節點 5，然后將該節點的 right 指針指向 root。并記錄 root 節點的值。

向左移動 p1，即 p1 = p1.left

p2 = p1.left ，即節點 4 ，找到 p1 的左子樹中的最右葉子節點，也就是 9，并將該節點的 right 指針指向 2。

繼續向左移動 p1，即 p1 = p1.left，p2 = p1.left。也就是節點 8。并將該節點的 right 指針指向 p1。

我們發現這一步給前兩步是一樣的，都是找到葉子節點，將其 right 指針指向 p1，此時我們完成了添加 right 指針的過程，下面我們繼續往下看。

我們繼續移動 p1 指針，p1 = p1.left。p2 = p.left。此時我們發現 p2 == null，即下圖此時我們需要移動 p1， 但是不再是 p1 = p1.left 而是 p1 = p1.right。也就是 4，繼續讓 p2 = p1.left。此時則為下圖這種情況

此時我們發現 p2.right ！= null 而是指向 4，說明此時我們已經添加過了 right 指針，所以去掉 right 指針，并讓 p1 = p1.right

下面則繼續移動 p1 ，按照規則繼續移動即可，遇到的情況已經在上面做出了舉例，所以下面我們就不繼續贅述啦，如果還不是特別理解的同學，可以再去看一遍動畫加深下印象。時間復雜度 O（n），空間復雜度 O（1）下面我們來看代碼吧。

代碼

class Solution {

public List《Integer》 preorderTraversal（TreeNode root） {

List《Integer》 list = new ArrayList《》（）;

if （root == null） {

return list;

}

TreeNode p1 = root; TreeNode p2 = null;

while （p1 ！= null） {

p2 = p1.left;

if （p2 ！= null） {

//找到左子樹的最右葉子節點

while （p2.right ！= null && p2.right ！= p1） {

p2 = p2.right;

}

//添加 right 指針，對應 right 指針為 null 的情況

if （p2.right == null） {

list.add（p1.val）;

p2.right = p1;

p1 = p1.left;

continue;

}

//對應 right 指針存在的情況，則去掉 right 指針

p2.right = null;

} else {

list.add（p1.val）;

}

//移動 p1

p1 = p1.right;

}

return list;

}

}

原文標題：把二叉樹揉碎（二）

文章出處：【微信公眾號：算法與數據結構】歡迎添加關注！文章轉載請注明出處。

責任編輯：haq