原題鏈接：
整體思路
三道題的解決思路可統(tǒng)一，模板也極其相似，比九章提供的更漂亮。
- 將二叉樹分為“左”（包括一路向左，經(jīng)過的所有實際左+根）、“右”（包括實際的右）兩種節(jié)點
- 使用同樣的順序?qū)ⅰ白蟆惫?jié)點入棧
- 在合適的時機(jī)轉(zhuǎn)向（轉(zhuǎn)向后，“右”節(jié)點即成為“左”節(jié)點）、訪問節(jié)點、或出棧
比如{1,2,3}，當(dāng)cur位于節(jié)點1時，1、2屬于“左”節(jié)點，3屬于“右”節(jié)點。DFS的非遞歸實現(xiàn)本質(zhì)上是在協(xié)調(diào)入棧、出棧和訪問，三種操作的順序。上述統(tǒng)一使得我們不再需要關(guān)注入棧順序，僅需要關(guān)注出棧和訪問（第3點），隨著更詳細(xì)的分析，你將更加體會到這種簡化帶來的好處。
將對節(jié)點的訪問定義為results.add(node.val);，分析如下：
先序&&中序：
先序和中序的情況是極其相似的。
- 先序的實際順序：根左右
- 中序的實際順序：左根右
使用上述思路，先序和中序的遍歷順序可統(tǒng)一為：“左”“右”。
給我們的直觀感覺是代碼也會比較相似。實際情況正是如此，先序與中序的區(qū)別只在于對“左”節(jié)點的訪問上。
先序的實現(xiàn)
不需要入棧，每次遍歷到“左”節(jié)點，立即輸出即可。
需要注意的是，遍歷到最左下的節(jié)點時，實際上輸出的已經(jīng)不再是實際的根節(jié)點，而是實際的左節(jié)點。這符合先序的定義。
while (cur != null) {
results.add(cur.val);
stack.push(cur);
cur = cur.left;
}
而后，因為我們已經(jīng)訪問過所有“左”節(jié)點，現(xiàn)在只需要將這些沒用的節(jié)點出棧，然后轉(zhuǎn)向到“右”節(jié)點。于是“右”節(jié)點也變成了“左”節(jié)點，后續(xù)處理同上。
if (!stack.empty()) {
cur = stack.pop();
// 轉(zhuǎn)向
cur = cur.right;
}
完整代碼如下：
private List<Integer> dfsPreOrder(TreeNode root) {
ArrayList<Integer> results = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.empty()) {
while (cur != null) {
results.add(cur.val);
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
// 轉(zhuǎn)向
cur = cur.right;
}
return results;
}
中序的實現(xiàn)
基于對先序的分析，先序與中序的區(qū)別只在于對“左”節(jié)點的處理上，我們調(diào)整一行代碼即可完成中序遍歷。
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
results.add(cur.val); // 僅調(diào)整該行代碼
// 轉(zhuǎn)向
cur = cur.right;
注意，我們在出棧之后才訪問這個節(jié)點。因為先序先訪問實際根，后訪問實際左，而中序恰好相反。相同的是，訪問完根+左子樹（先序）或左子樹+根（中序）后，都需要轉(zhuǎn)向到“右”節(jié)點，使“右”節(jié)點稱為新的“左”節(jié)點。
完整代碼如下：
private List<Integer> dfsInOrder(TreeNode root) {
List<Integer> results = new ArrayList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while (cur != null || !stack.empty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
results.add(cur.val);
cur = cur.right;
}
return results;
}
后序
后序的情況略有不同，但仍然十分簡潔。
- 后序的實際順序：左右根
入棧順序不變，我們只需要考慮第3點的變化（合適時機(jī)轉(zhuǎn)向）。出棧的對象一定都是“左”節(jié)點（“右”節(jié)點會在轉(zhuǎn)向后稱為“左”節(jié)點，然后入棧），也就是實際的左或根；實際的左可以當(dāng)做左右子樹都為null的根，所以我們只需要分析實際的根。
對于實際的根，需要保證先后訪問了左子樹、右子樹之后，才能訪問根。實際的右節(jié)點、左節(jié)點、根節(jié)點都會成為“左”節(jié)點入棧，所以我們只需要在出棧之前，將該節(jié)點視作實際的根節(jié)點，并檢查其右子樹是否已被訪問即可。如果不存在右子樹，或右子樹已被訪問了，那么可以訪問根節(jié)點，出棧，并不需要轉(zhuǎn)向；如果還沒有訪問，就轉(zhuǎn)向，使其“右”節(jié)點成為“左”節(jié)點，等著它先被訪問之后，再來訪問根節(jié)點。
所以，我們需要增加一個標(biāo)志，記錄右子樹的訪問情況。由于訪問根節(jié)點前，一定先緊挨著訪問了其右子樹，所以我們只需要一個標(biāo)志位。
完整代碼如下：
private List<Integer> dfsPostOrder(TreeNode root) {
List<Integer> results = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode last = null;
while(cur != null || !stack.empty()){
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.peek();
if (cur.right == null || cur.right == last) {
results.add(cur.val);
stack.pop();
// 記錄上一個訪問的節(jié)點
// 用于判斷“訪問根節(jié)點之前，右子樹是否已訪問過”
last = cur;
// 表示不需要轉(zhuǎn)向，繼續(xù)彈棧
cur = null;
} else {
cur = cur.right;
}
}
return results;
}
總結(jié)
思路簡潔萬歲！模板大法萬歲！
消滅人類暴政，世界屬于三體！
本文鏈接：【刷題】二叉樹非遞歸遍歷
作者：猴子007
出處：https://monkeysayhi.github.io
本文基于 知識共享署名-相同方式共享 4.0 國際許可協(xié)議發(fā)布，歡迎轉(zhuǎn)載，演繹或用于商業(yè)目的，但是必須保留本文的署名及鏈接。
