94. 二叉樹的中序遍歷

思路

1. 首先不斷壓入左節點，一直到葉節點之後停止。
2. 彈出節點，此時左邊的路已經走過，當前節點是中，加入到遍歷順序中。
3. 壓入右節點，再重複步驟1。

程式碼

1. 用棧實現中序遍歷

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;

        auto pushLeft = [&](TreeNode* node) {
            while(node) {
                stk.push(node);
                node = node->left;
            }
        };
        
        pushLeft(root); // 壓入最左的一條路
        while(!stk.empty()) {
            TreeNode* cur = stk.top(); stk.pop();
            res.push_back(cur->val); // 取出節點, 並輸出 (中) 
            if(cur->right) pushLeft(cur->right); // 壓入右樹最左的一條路
        }
        return res;
    }
};

2. 用棧實現中序遍歷

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* head = root;
        while(!stk.empty() || head != nullptr) { // 棧非空 或 節點非空, 棧非空表示還有節點沒加入, 節點非空也代表還沒加入(加入後會指向 right)
            if(head) { // 非空, 繼續往左走直到空
                stk.push(head);
                head = head->left;
            }
            else { // 空, 表示走到底, 可以開始 pop 了
                head = stk.top(); stk.pop();
                res.push_back(head->val);
                head = head->right; // 往右邊走, 如果此時非空, 會繼續往左走直到空
            }
        }
        return res;
    }
};

3. 遞迴

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

複雜度分析

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