演算法 - 二叉樹遍歷的10種方法，你都會了么？（三）（非遞歸後序遍歷）

書接上回，因為後序遍歷是非尾調用的遞歸，用一個棧實現遍歷比較複雜。

下面我們就來講，使用一個棧的後序遍歷怎麼實現。

思路一：

我們可以採用和先序，中序遍歷相同的思路壓棧。

但是當我們經過某節點，走向其右子樹時，不使用該節點，所以我們應該把該節點再次壓棧。

我們訪問某節點的條件是：該節點沒有孩子，或者右邊孩子已經被訪問過。

請注意這樣一個事實：當我們後序遍歷某個結點時，我們上一個訪問的元素必然是其右子節點,所以我們可以用pre來記錄上一個訪問的元素，進行條件判斷。

代碼如下：

public void traverse(TreeNode root){ Stack<TreeNode> stack = new Stack<>(); TreeNode node = root; TreeNode pre = null; while(node != null){ stack.push(node); node = node.left; } while(!stack.empty()){ node = stack.pop(); if(node.right != null && node.right != pre){ stack.push(node); node = node.right; while(node != null){ stack.push(node); node = node.right; } }else{ //visit 後序 pre = node; } }}

這種遍歷，有一個好玩的地方，就是：在代碼運行到//visit 後序那裡時，棧中的元素，剛好是node的所有祖先 。

這是因為：① 當我們遍歷某節點時，其「右上方」的任何節點，還沒有被經過（pass）。

這其實是『先序』的入棧方式決定的。

② 當我們遍歷右節點時，其左節點必然已經出棧。

這是由後序遍歷的出棧方式決定的。

另一種寫法：

public void traverse(TreeNode root){ Stack<TreeNode> stack = new Stack<>(); TreeNode node = root; TreeNode pre = null; while(node != null || !stack.empty()){ if(node != null){ stack.push(node); node = node.left; }else{ node = stack.pop(); if(node.right != null && node.right != pre){ stack.push(node); node = node.right; }else{ //visit 後序 pre = node; node = null; } } }}

思路二：

思路一是採用回溯的思想，利用pre節點，把每個父節點入棧（pass）了兩次。

那麼如果我們從根節點遍歷的時候，把右子節點A在其之前入棧，出棧時，通過判斷棧頂元素是否為右節點A，就能根據這個條件進入右子樹。

代碼如下：

public void traverse(TreeNode root){ if (root == null) return; TreeNode cur, pre = null; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.empty()) { cur = stack.peek(); if (pre == null || pre.left == cur || pre.right == cur) { if (cur.left != null) stack.push(cur.left); else if (cur.right != null) stack.push(cur.right); else { stack.pop(); //visit 後序 } } else if (cur.left == pre) { if (cur.right != null) stack.push(cur.right); else { stack.pop(); //visit 後序 } } else if (cur.right == pre) { stack.pop(); //visit 後序 } pre = cur; } }}

唉，人這一輩子啊，總要有一些看不懂的代碼。55555

下一篇，我們看一下Morris遍歷，一種不用棧也不用遞歸的遍歷方式~ 還有BFS（廣度優先搜索），也就是層次遍歷。