LeetCode 144 二叉樹前序遍歷：非遞歸棧模擬法詳解

題目要求

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

棧模擬核心邏輯

前序遍歷訪問節點後需先處理左子樹，右子樹暫存。利用棧後進先出特性：

1. 當前節點 cur 入棧前先訪問（加入結果）。
2. 右子節點先入棧（後處理），左子節點賦給 cur 繼續循環。
3. cur 為空時彈棧頂繼續。

Java 參考代碼

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> st = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !st.isEmpty()) {
        while (cur != null) {
            res.add(cur.val);          // 訪問根
            if (cur.right != null)     // 右子節點入棧
                st.push(cur.right);
            cur = cur.left;            // 轉向左子樹
        }
        if (!st.isEmpty())
            cur = st.pop();            // 取出右子樹根
    }
    return res;
}

C++ 版本

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) {
            res.push_back(cur->val);
            if (cur->right) st.push(cur->right);
            cur = cur->left;
        }
        if (!st.empty()) {
            cur = st.top(); st.pop();
        }
    }
    return res;
}

另一種通用棧寫法（統一風格）

stack<TreeNode*> st;
if (root) 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);
}

此法將「訪問」與「展開子節點」合併，代碼更短，但需注意入棧順序相反。

複雜度

• 時間 O(n)：每節點進棧出棧各一次。
• 空間 O(h)：h 為樹高，最壞 O(n)。

遞歸與非遞歸對比