LeetCode 二叉樹層次遍歷：隊列 BFS 實現

題目重述

給定二叉樹根節點，返回逐層節點值列表。例如 {3,9,20,#,#,15,7} 輸出 [[3],[9,20],[15,7]]。

C++ 標準解法

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int sz = q.size();
            vector<int> level;
            level.reserve(sz);
            while (sz--) {
                TreeNode* node = q.front(); q.pop();
                level.push_back(node->val);
                if (node->left)  q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res.push_back(move(level));
        }
        return res;
    }
};

關鍵點

• 用 q.size() 固化當前層節點數，避免層混淆。
• reserve 減少向量擴容開銷。
• move 避免拷貝大向量（C++11）。
• 時間 O(n)，空間 O(n)（最寬層節點數）。

Java 版本對比

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        List<Integer> level = new ArrayList<>(sz);
        for (int i=0; i