144. 二叉樹的前序遍歷

思路

現在要用stack去實現中序遍歷，先輸出中間節點，接下來要先左再右，因此壓入棧時，要先右再左。

程式碼

1. 用棧實現前序遍歷

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

2. 遞迴

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

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$