二叉树的层序遍历

1
#include <queue>
2
#include <vector>
3

4
class Solution {
5
public:
6
    vector<vector<int>> levelOrder(TreeNode* root) {
7
        vector<vector<int>> ans;
8
        if (!root) return ans;
9

10
        queue<TreeNode*> q;
11
        q.push(root);
12

13
        while (!q.empty()) {
14
            // 关键：在进入本层循环前，记录当前队列长度
15
            int sz = q.size();
16
            vector<int> curLevel;
17

18
            // 严格出队 sz 个节点，这些节点恰好属于同一层
19
            for (int i = 0; i < sz; ++i) {
20
                TreeNode* node = q.front();
21
                q.pop();
22
                curLevel.push_back(node->val);
23

24
                // 将下一层节点加入队尾（此时不会在当前 for 循环中被处理）
25
                if (node->left) q.push(node->left);
26
                if (node->right) q.push(node->right);
27
            }
28
            // 使用 move 避免不必要的 vector 拷贝
29
            ans.push_back(move(curLevel));
30
        }
31
        return ans;
32
    }
33
};