1. 題目鏈接

94. 二叉樹的中序遍歷 - 力扣（LeetCode）

2. 題目描述

給定一個二叉樹的根節點 root ，返回 它的 中序 遍歷 。

3. 題目示例

示例 1 :

輸入：root = [1,null,2,3]
輸出：[1,3,2]

示例 2 :

輸入：root = []
輸出：[]

4. 解題思路

1. 顏色標記法：
   • 使用顏色標記節點狀態：1（未訪問）、2（已訪問）
   • 模擬遞歸棧的調用過程，但通過顯式棧實現
2. 棧操作順序：
   • 對于未訪問節點（color=1），按"右-根-左"順序入棧
   • 這樣出棧順序就是"左-根-右"，符合中序遍歷要求
3. 關鍵點：
   • 通過顏色標記避免重復處理
   • 顯式棧替代遞歸調用棧
   • 空節點直接跳過

5. 題解代碼

class Solution {// 輔助節點類，用于標記節點狀態class Node {TreeNode node;  // 樹節點int color;      // 顏色標記：1表示未訪問，2表示已訪問Node(TreeNode node, int color) {this.node = node;this.color = color;}}// 中序遍歷方法public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();  // 存儲遍歷結果Deque<Node> stack = new LinkedList<>();  // 使用雙端隊列模擬棧// 空樹直接返回if (root == null) return ans;// 初始狀態：根節點標記為未訪問stack.push(new Node(root, 1));while (!stack.isEmpty()) {Node cur = stack.pop();  // 彈出棧頂元素// 跳過空節點if (cur.node == null) continue;if (cur.color == 1) {  // 未訪問節點// 按照"右-根-左"順序入棧（出棧順序為"左-根-右"）stack.push(new Node(cur.node.right, 1));  // 右子節點（未訪問）stack.push(new Node(cur.node, 2));        // 當前節點標記為已訪問stack.push(new Node(cur.node.left, 1));   // 左子節點（未訪問）} else {  // 已訪問節點ans.add(cur.node.val);  // 添加到結果列表}}return ans;}
}

6. 復雜度分析

1. 時間復雜度：O(n)
   • 每個節點被訪問兩次（入棧和出棧）
   • 但常數系數為2，仍為線性復雜度
2. 空間復雜度：O(n)
   • 棧的最大深度等于樹的高度
   • 最壞情況下（斜樹）為O(n)