102. 二叉樹的層序遍歷

思路

想要層序遍歷，先要拿第一層的內容，再拿第二層的內容…。
第一層就是根節點root。
第二層是root的左節點left和右節點right。
第三層是left的左右節點和right的左右節點。

因此，我們每次獲取上一層節點的左右節點，就是這一層的答案，也做為獲取下一層的依據。

1. 我們用queue去紀錄每層節點的內容，並紀錄當前queue的大小size。（代表當前層的節點數量）
2. 從queue當中拿出size次節點，被拿出來的節點都在同一層，紀錄到答案當中。
3. 在拿出節點的同時，把節點的左右節點放到queue當中，為下一層的紀錄做準備。

除了用內建的 STL 之外，也能用陣列去做到一樣的效果，在題目有更多變化時，用陣列的方法做能方便根據情況去做修改。

程式碼

1. 隊列

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr) return {};
        queue<TreeNode*> q;
        q.push(root); // 第一層的節點為 root 
        vector<vector<int>> res;
        TreeNode* cur = nullptr;
        while(!q.empty()) {
            int size = q.size(); // 取得當前這層的大小
            vector<int> add;
            while(size--) { // 把這層的所有節點取出，並將下一層的節點加入
                cur = q.front();
                q.pop();
                if(cur->left != nullptr) {
                    q.push(cur->left);
                }
                if(cur->right != nullptr) {
                    q.push(cur->right);
                }
                add.push_back(cur->val);
            }
            res.push_back(add);
        }
        return res;
    }
};

2. 陣列模擬隊列

class Solution {
private:
    const int MX = 2000;
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr) return {};
        vector<vector<int>> res;
        vector<TreeNode*> q(MX + 1);
        int left = 0, right = 0;
        q[right++] = root;
        while(left < right) {
            int size = right - left; // 左閉右開
            vector<int> add;
            while(size--) {
                TreeNode* cur = q[left++];
                add.push_back(cur->val);
                if(cur->left != nullptr) {
                    q[right++] = cur->left;
                }
                if(cur->right != nullptr) {
                    q[right++] = cur->right;
                }
            }
            res.push_back(add);
        }
        return res;
    }
};

複雜度分析

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