Tree-Traversal-Iterative

這篇在解決什麼

遞迴的三種 DFS 順序只差一行的位置，改起來毫無難度：

void dfs(TreeNode* node) {
  if (!node) return;
  // visit(node);   ← 放這裡是前序
  dfs(node->left);
  // visit(node);   ← 放這裡是中序
  dfs(node->right);
  // visit(node);   ← 放這裡是後序
}

換成迭代就不是這樣了。遞迴堆疊幫你記住的不只是「還沒走的節點」，還有「這個節點走到第幾步」——自己拿 stack 模擬時，那個隱含的狀態要另外想辦法表達，於是三種順序變成三種難度：前序最簡單、中序要換一種骨架、後序還得再解決「右子樹回來過了沒」。

這篇收三套專用模板 + 一套統一模板 + Morris，都用 3000 棵隨機樹對照遞迴驗過。

        1              前序 根左右：1 2 4 5 3 6
      /   \            中序 左根右：4 2 5 1 6 3
     2     3           後序 左右根：4 5 2 6 3 1
    / \   /
   4   5 6             三種順序的差別只在「根」在哪個位置被輸出，
                       左右子樹的相對順序永遠是左先右後

模板一：前序 — 直接拿 stack 當待辦清單

前序特別簡單，因為看到節點就能立刻輸出，不需要記任何狀態。stack 純粹是「還沒處理的節點」清單。

// Time: O(n)   每個節點進出 stack 各一次
// Space: O(h)  stack 最多裝一條根到葉的路徑上的兄弟節點
vector<int> preorderTraversal(TreeNode* root) {
  vector<int> out;
  if (!root) {
    return out;
  }
  stack<TreeNode*> st;
  st.push(root);
  while (!st.empty()) {
    TreeNode* node = st.top();
    st.pop();
    out.push_back(node->val);
    if (node->right) {
      st.push(node->right);
    }
    if (node->left) {
      st.push(node->left);
    }
  }
  return out;
}

模板二：中序 — 一路往左的骨架（最該背熟的一個）

中序不能看到節點就輸出：走到 1 的時候，左子樹還沒走完，1 還不能出場。所以骨架改成兩段式——內層 while 一路往左把路徑壓進 stack，彈出時才輸出，然後轉向右子樹。

// Time: O(n)
// Space: O(h)
vector<int> inorderTraversal(TreeNode* root) {
  vector<int> out;
  stack<TreeNode*> st;
  TreeNode* cur = root;
  while (cur || !st.empty()) {
    while (cur) {          // 一路往左，把沿路的節點都欠著
      st.push(cur);
      cur = cur->left;
    }
    cur = st.top();        // 左邊走到底了，這個節點可以輸出
    st.pop();
    out.push_back(cur->val);
    cur = cur->right;      // 轉向右子樹，下一輪繼續往左鑽
  }
  return out;
}

前序也能套同一骨架

值得知道但不必特地改用：把 push_back 從彈出後搬到壓入時，同一個骨架就變成前序。這正好對應遞迴那三個 visit() 位置。

while (cur || !st.empty()) {
  while (cur) {
    out.push_back(cur->val);   // ← 只有這一行搬了位置
    st.push(cur);
    cur = cur->left;
  }
  cur = st.top();
  st.pop();
  cur = cur->right;
}

模板三：後序 — 兩種寫法，難度差很多

後序最麻煩：一個節點被彈出時，你不知道它的右子樹是「還沒走」還是「剛走完回來」。兩種解法各自繞開這個問題。

寫法 A：走成「根右左」再整個反轉 — 好寫但要多一次 reverse

根左右 反過來是 右左根，而 左右根（後序）反過來是 根右左。所以把模板一的 push 順序對調、得到「根右左」，最後 reverse 一次就是後序。

// Time: O(n)   多一次 O(n) 反轉
// Space: O(h)  不算輸出陣列
vector<int> postorderTraversal(TreeNode* root) {
  vector<int> out;
  if (!root) {
    return out;
  }
  stack<TreeNode*> st;
  st.push(root);
  while (!st.empty()) {
    TreeNode* node = st.top();
    st.pop();
    out.push_back(node->val);
    if (node->left) {         // 和模板一相反：先推左，讓右先被處理
      st.push(node->left);
    }
    if (node->right) {
      st.push(node->right);
    }
  }
  reverse(out.begin(), out.end());
  return out;
}

寫法 B：真後序，用 last 記住剛走完的子樹

沿用模板二的骨架，多一個 last 指標。peek 的右子樹存在且不是剛回來的那棵，就先去走右邊；否則代表左右都完成了，可以輸出自己。

// Time: O(n)
// Space: O(h)
vector<int> postorderTraversal(TreeNode* root) {
  vector<int> out;
  stack<TreeNode*> st;
  TreeNode *cur = root, *last = nullptr;
  while (cur || !st.empty()) {
    while (cur) {
      st.push(cur);
      cur = cur->left;
    }
    TreeNode* peek = st.top();
    if (peek->right && peek->right != last) {
      cur = peek->right;      // 右邊還沒走，去走右邊（先不 pop）
    } else {
      out.push_back(peek->val);
      last = peek;            // 記住「我這棵子樹走完了」
      st.pop();
    }
  }
  return out;
}

統一模板：NULL 標記法 — 一套骨架三種順序

如果不想背三套，可以只背這一套：節點被推兩次，第二次推的後面緊跟一個 nullptr 當標記。彈出時看到 nullptr 就代表「下一個才是該輸出的」，否則就是「展開這個節點」。改順序只要改 push 的排列。

// Time: O(n)   每個節點被 push 兩次
// Space: O(h)  但常數 ~3 倍
vector<int> traversal(TreeNode* root) {
  vector<int> out;
  stack<TreeNode*> st;
  if (root) {
    st.push(root);
  }
  while (!st.empty()) {
    TreeNode* node = st.top();
    st.pop();
    if (node) {
      // 逆序推入：想先處理的最後推。以下是中序（左根右）
      if (node->right) {
        st.push(node->right);
      }
      st.push(node);
      st.push(nullptr);       // 標記：node 自己已就緒，還沒輸出
      if (node->left) {
        st.push(node->left);
      }
    } else {
      out.push_back(st.top()->val);
      st.pop();
    }
  }
  return out;
}

三種順序只差 push 的排列（都記得逆著寫）：

滿二元樹 n = 1048575        時間        stack 峰值
  中序專用模板              3.4-3.8 ms      20
  統一模板（NULL 標記）      3.9-4.8 ms      59

隨機樹   n = 1000000        時間        stack 峰值
  中序專用模板              7.5-10.6 ms     30
  統一模板（NULL 標記）      9.5-12.5 ms     90

Morris：O(1) 空間，代價是暫時改動樹

不用 stack，改成把「左子樹最右節點」的空 right 指標暫時接回目前節點當作回程線索，走過後再拆掉。

// Time: O(n)   每條邊最多走兩次
// Space: O(1)  不含輸出
vector<int> inorderTraversal(TreeNode* root) {
  vector<int> out;
  TreeNode* cur = root;
  while (cur) {
    if (!cur->left) {
      out.push_back(cur->val);
      cur = cur->right;
    } else {
      TreeNode* pred = cur->left;                    // 找中序前驅
      while (pred->right && pred->right != cur) {
        pred = pred->right;
      }
      if (!pred->right) {
        pred->right = cur;                           // 架線
        cur = cur->left;
      } else {
        pred->right = nullptr;                       // 拆線（第二次來到）
        out.push_back(cur->val);
        cur = cur->right;
      }
    }
  }
  return out;
}

把 out.push_back(cur->val) 從「拆線那支」搬到「架線那支」（if (!pred->right) 裡面）就是 Morris 前序。後序也做得到，但要反轉右邊界鏈、程式碼長度翻倍，實務上不值得。

怎麼選

題目分類

後序那一列的三題在 LeetCode 上都寫成遞迴，列在這裡是因為它們的資訊流動方向是後序——子樹先回報、父節點才能算——正是寫法 A 幫不上忙、寫法 B 才能改寫的那一類。

Related Problems

0094-Binary-Tree-Inorder-Traversal — 模板二最乾淨的原型
0144-Binary-Tree-Preorder-Traversal — 模板一最乾淨的原型
0145-Binary-Tree-Postorder-Traversal — 模板三兩種寫法的對照場
0098-Validate-Binary-Search-Tree — 模板二 + 一個 prev 指標的代表題
0230-Kth-Smallest-Element-in-a-BST — 模板二 + 提早 return 的代表題
0173-Binary-Search-Tree-Iterator — 把模板二拆成 class 狀態，迭代非用不可的場合