演算法 - 二叉樹的10種遍歷方法，你都會了么?( 二 )

在上一篇文章（二叉樹的遍歷( 一 )）中，我們通過思考函數入棧出棧的過程，理解了遞歸遍歷二叉樹的原理，下面我們來理解非遞歸的寫法。

在遞歸遍歷中，我們發現，程序首先把根節點的左子孫依次入棧，所以我們可以有如下代碼：

public void traverse1(TreeNode root){ if(root == null) return; Stack<TreeNode> stack = new Stack<>(); TreeNode nodeee = root; while(node != null){ //visit 先序 stack.push(node); node = node.left; }

然後，如果棧不為空，依次出棧，看其是否有右子節點，如果有右節點，執行上一步操作：

while (stack.size() > 0) { node = stack.pop(); //visit 中序 if (node.right != null) { node = node.right; while (node != null) { stack.push(node); node = node.left; } } }}

那麼，先序遍歷的visit點，就在stack.push()之前；中序遍歷的visit點，就在stack.pop() 之後。

上面這兩段代碼可以優化為下面一個循環：

public static void traverse2(TreeNode root){ if(root == null) return; Stack<TreeNode> stack = new Stack<>(); TreeNode node = root; while(!(node==null && stack.empty())){ while(node != null){ //visit 先序 stack.push(node); node = node.left; } node = stack.pop(); //visit 中序 node = node.right; } }

這樣就實現了非遞歸的先序遍歷和中序遍歷。

還有另一種方式實現非遞歸的先序遍歷，用了深度優先搜索（DFS）的思想，其實，二叉樹的先序遍歷，中序遍歷，後序遍歷，都是深度優先搜索。

深度優先搜索：

首先，把根節點入棧。 ①

如果棧不為空，彈出棧頂元素。 ②

把該元素的子節點入棧。 ③

循環②，③，直到棧為空。④

那麼，我們只要保證右節點先於左入棧，就能實現」根->左->右「的先序遍歷。

代碼如下：

public static void traverse3(TreeNode root){ Stack<TreeNode> stack = new Stack<>(); stack.push(root); while(!stack.empty()){ TreeNode node = stack.pop(); //visit 先序 if(node.right != null){ stack.push(node.right); } if(node.left != null) { stack.push(node.left); } } }

從這個思想出發，我們可以很簡單的實現另一種遍歷：」根->右->左「遍歷。

雖然這種遍歷沒有名字，但是他是後序遍歷的反序。所以我們可以利用兩個棧，利用棧的LIFO特點，來實現後續遍歷。

代碼如下：

public static void traverse4(TreeNode root){ Stack<TreeNode> stack = new Stack<>(); Stack<TreeNode> result = new Stack<>(); stack.push(root); while(!stack.empty()){ TreeNode node = stack.pop(); //visit 根->右->左 result.push(node); if(node.left != null) { stack.push(node.left); } if(node.right != null){ stack.push(node.right); } } while(!result.empty()){ node = result.pop(); //visit 後序 } }

那麼，怎麼用一個棧來實現後序遍歷呢？

下面的文章會講到。

為什麼我們模擬程序棧的時候，沒有後續遍歷的visit點呢？

這主要是因為後序遍歷是非尾遞歸的，深層的原因，之後可能會講到。

咳咳，歡迎關注，歡迎點贊，歡迎評論哦~~