二叉樹的遍歷

雖然用遞歸的方法遍歷二叉樹實現起來更簡單，但是要想深入理解二叉樹的遍歷，我們還必須要掌握用棧遍歷二叉樹，遞歸其實就是利用了系統棧去遍歷。特此記錄一下如何用雙重視角去看待二叉樹的遍歷，加深一下理解。

前序遍歷

我們從前序遍歷入手，搞懂了一個，其它的也就容易了。

使用遞歸的方法遍歷的話很簡單，代碼如下：

public void preorderTraversal(TreeNode root, List<Integer> result) {if (root == null) {return;}// 訪問根節點result.add(root.val);// 遞歸遍歷左子樹preorderTraversal(root.left, result);// 遞歸遍歷右子樹preorderTraversal(root.right, result);
}

它利用了系統中線程的棧空間，先訪問當前節點，再調用自身方法遞歸地去對左子節點進行前序遍歷，這在線程棧空間中會新增加一個方法。線程也會優先去處理在線程棧上新增的方法。如下圖所示：

這里發生的事情是：

1. 系統為每次方法調用維護一個執行上下文，包含局部變量和返回地址
2. 當執行到preorder(root.left)時，當前方法的執行被暫停，其狀態被保存在系統棧中
3. 系統轉而執行左子樹的遍歷，完成后會自動返回到保存的執行點
4. 繼續執行preorder(root.right)

關鍵點是：系統棧自動保存了"接下來要做什么"的信息。每個節點被處理時，系統知道處理完左子樹后還需要回來處理右子樹。

而使用棧的話，我們只需要按照遞歸遍歷的方式自己創建一個棧模擬著線程棧的方法去遍歷就行。代碼如下：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) return result;Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();result.add(node.val);// 先右后左入棧，這樣出棧時會先處理左子節點if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}}return result;
}

這里的關鍵區別是：

1. 我們只能用棧存儲節點本身，而不能存儲"執行到哪一步"的完整上下文
2. 棧頂元素是下一個要處理的節點，而不是一個帶有執行狀態的方法調用
3. 由于棧的后進先出特性，為了先處理左子節點，必須先將右子節點入棧，再將左子節點入棧

系統線程棧和手動實現棧的區別：

1. 系統線程棧的一個棧幀的運行（不包括遞歸調用產生的跳轉）等同于手動實現棧的三件事：1.訪問當前節點 2.入棧右子節點 3.入棧左子節點
2. 系統線程棧新增了一個棧幀等同于手動實現棧的：出棧一個節點作為當前節點

中序遍歷

遞歸代碼如下：

public void inorderTraversal(TreeNode root, List<Integer> result) {if (root == null) {return;}// 遞歸遍歷左子樹inorderTraversal(root.left, result);// 訪問根節點result.add(root.val);// 遞歸遍歷右子樹inorderTraversal(root.right, result);
}

系統線程棧中一個棧幀的執行過程（不包括遞歸調用產生的跳轉）等同于手動實現棧中的三個操作：

1. 遞歸訪問左子樹
2. 訪問當前節點
3. 遞歸訪問右子樹

手動實現棧代碼如下：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode current = root;while (current != null || !stack.isEmpty()) {// 將所有左子節點入棧while (current != null) {stack.push(current);current = current.left;}// 處理棧頂節點current = stack.pop();result.add(current.val);// 轉向右子樹current = current.right;}return result;
}

核心思路是先將當前節點及其所有左子節點入棧，然后訪問節點值，再處理右子樹
無法用簡單的"入棧-出棧-訪問"模式表達，需要維護一個current指針跟蹤當前處理節點
關鍵步驟：

1. 將當前節點及其所有左子節點入棧
2. 彈出棧頂節點并訪問
3. 將當前節點切換到右子節點，重復步驟1

后續遍歷

遞歸代碼如下：

public void postorderTraversal(TreeNode root, List<Integer> result) {if (root == null) {return;}// 遞歸遍歷左子樹postorderTraversal(root.left, result);// 遞歸遍歷右子樹postorderTraversal(root.right, result);// 訪問根節點result.add(root.val);
}

系統線程棧中一個棧幀的執行過程等同于手動實現棧中的三個操作：

1. 遞歸訪問左子樹
2. 遞歸訪問右子樹
3. 訪問當前節點

手動實現棧代碼如下：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) return result;Stack<TreeNode> stack1 = new Stack<>();Stack<TreeNode> stack2 = new Stack<>();stack1.push(root);// 先將節點按 根-右-左 的順序放入棧2while (!stack1.isEmpty()) {TreeNode node = stack1.pop();stack2.push(node);if (node.left != null) {stack1.push(node.left);}if (node.right != null) {stack1.push(node.right);}}// 從棧2中彈出的順序就是 左-右-根while (!stack2.isEmpty()) {result.add(stack2.pop().val);}return result;
}

雙棧法
系統線程棧中一個棧幀的執行等同于：

1. 將當前節點壓入第二個棧（結果棧）
2. 將左子節點壓入第一個棧（處理棧）
3. 將右子節點壓入第一個棧（處理棧）

注意：入棧順序是"左-右"，這樣處理順序變成"右-左"，最終從結果棧彈出時順序為"左-右-根"

單棧法

1. 需要額外記錄上次訪問的節點
2. 核心思路是判斷右子樹是否已訪問，決定是訪問節點還是處理右子樹
3. 由于邏輯較復雜，難以用簡單的等價操作表述

總結

讀者可以根據前序遍歷的思路自行去理解中序遍歷和后序遍歷。重點就是理解系統的線程棧是怎么運作的，以及手動實現的棧是如何保存節點的。搞清楚了這兩點，對二叉樹的遍歷的理解就會更上一層了。