LeetCode Binary Tree Preorder Traversal：二叉樹前序遍歷

題目描述

給定二叉樹，返回前序遍歷結果。例：{1,#,2,3} → [1,2,3]。要求嘗試非遞歸實現。

遞歸解法

class Solution {
    void preorder(TreeNode* root, vector<int>& res) {
        if (root) {
            res.push_back(root->val);
            preorder(root->left, res);
            preorder(root->right, res);
        }
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res; preorder(root, res); return res;
    }
};

非遞歸：顯式棧

前序：根 → 左 → 右。棧先壓右再壓左，彈出即先處理左。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        stack<TreeNode*> 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) 棧/遞歸深度。