剑指Offer-从上到下打印二叉树II

📝题目

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：
[
  [3],
  [9,20],
  [15,7]
]

限制：节点总数 <= 1000

📝思路

树的层次遍历是简单的，本题在层次遍历的基础上增加了按层打印的要求。起初我以为可以计算每层的节点，但明显地，当存在大量 null 节点时计数是不准确的。
注意到，在层次遍历过程中左右子节点总是同时入队的，即当前队列中所有的节点都属于同一层，此时问题就迎刃而解了。

📝题解

vector<vector<int>> levelOrder(TreeNode* root) {
    queue<TreeNode*> q;
    vector<vector<int>> res;

    q.push(root);
    vector<int> inner;
    while (!q.empty()) {
        int len = q.size();                 /* 关键代码 */
        for (int i = 0; i < len; i++) {
            TreeNode* tmp = q.front();
            q.pop();

            if (tmp != NULL) {
                inner.push_back(tmp->val);
                q.push(tmp->left);
                q.push(tmp->right);
            }
        }
        if (!inner.empty()) {
            res.push_back(inner);
            inner.clear();
        }
    }
    return res;
}