LeetCode 144 Binary Tree Preorder Traversal：非遞迴前序遍歷完整解法

題目

給定二元樹根節點，回傳前序遍歷 (根→左→右) 節點值列表。要求非遞迴實作。

方法一：顯式堆疊模擬遞迴 (標準解)

/**
 * Definition for a binary tree node.
 * struct TreeNode { int val; TreeNode *left; TreeNode *right; };
 */
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;
    }
};

原理：堆疊後進先出，先處理根，再將右子樹、左子樹根節點壓入，下一次迴圈先彈出左子樹根，符合前序。

方法二：Morris Traversal (O(1) 空間，線索化)

class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
        vector res;
        TreeNode* cur = root;
        while (cur) {
            if (!cur->left) {
                res.push_back(cur->val);
                cur = cur->right;
            } else {
                // 找左子樹最右節點 (前驅)
                TreeNode* pre = cur->left;
                while (pre->right && pre->right != cur) pre = pre->right;
                if (!pre->right) {
                    // 建立線索
                    pre->right = cur;
                    res.push_back(cur->val); // 訪問根
                    cur = cur->left;
                } else {
                    // 恢復樹結構
                    pre->right = nullptr;
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};

優點：無額外空間 (除輸出)。缺點：修改樹結構 (需恢復)、較難理解。

方法三：雙棧/隊列法 (原碼思路，較繁瑣)

原碼用隊列存左子樹、棧存右子樹，優先展開左鏈。雖可行但非標準模式，不推薦面試使用。

複雜度對比

總結

面試首選顯式堆疊法：邏輯清晰、易擴展至中序/後序 (只需調整壓棧/輸出順序)。Morris 遍歷作為進階加分項了解即可。