LeetCode Binary Tree Preorder Traversal：非遞歸前序遍歷

問題描述

給定二叉樹根節點，返回前序遍歷結果（根→左→右）。要求非遞歸實現。

棧模擬遞歸

遞歸本質是系統棧保存調用幀。手動用棧：
1. 根節點入棧
2. 彈出節點，訪問值
3. 右子節點先入棧，左子節點後入棧（棧先進後出，保證左先處理）
4. 重複直到棧空

完整代碼

class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
        vector res;
        if (!root) return res;
        stack st;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top(); st.pop();
            res.push_back(node->val);
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return res;
    }
};

關鍵點

• 右子節點先入棧，左子節點後入棧 → 出棧順序：左 → 右
• 時間 O(n)，空間 O(h) (h 為樹高，最壞 O(n))
• 遞歸版本僅供參考：void dfs(root) { if(!root) return; res.push_back(root->val); dfs(root->left); dfs(root->right); }

統一框架：顏色標記法

通用非遞歸模板（支持前/中/後序）：

struct Command { TreeNode* node; string op; }; // op: "go"=遍歷, "print"=訪問
vector preorderTraversal(TreeNode* root) {
    vector res;
    stack st;
    if (root) st.push({root, "go"});
    while (!st.empty()) {
        auto [node, op] = st.top(); st.pop();
        if (!node) continue;
        if (op == "print") res.push_back(node->val);
        else {
            // 前序：print → go(left) → go(right) 入棧順序反過來
            if (node->right) st.push({node->right, "go"});
            if (node->left) st.push({node->left, "go"});
            st.push({node, "print"});
        }
    }
    return res;
}

顏色標記法將遞歸調用展開為顯式指令，統一處理三種遍歷，是面試中展示深度理解的加分項。