Link to LeetCode Problem

S1: 递归

用 DFS 的方式来获取层级遍历结果，使用一个额外变量来记录当前层级的深度。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> results;
        helper(root, 0, results);
        return results;
    }
    void helper(TreeNode* root, int depth, vector<vector<int>>& results) {
        if (root == nullptr) return;
        if (depth == results.size()) {
            results.push_back(vector<int>());
        }
        results[depth].push_back(root->val);

        helper(root->left, depth + 1, results);
        helper(root->right, depth + 1, results);
    }
};

• Time: $O(N)$，N 是二叉树的节点总数。
• Space: $O(logN)$，当二叉树退化成链表的时候，空间复杂度会变成 $O(N)$。

S2: 循环+队列

伪代码：

新建一个队列 q 来存放遍历的节点
把 root 推入队列

while q is not empty：
  记录当前层级的节点数 nodeCount (即队列中的节点数)
  新建一个数组来存放当前层级的遍历结果

  while nodeCount-- > 0:
    出列一个节点
    将它的值放入当前层级遍历结果中
    将它的左右子节点入列

  当前层级遍历结束，此时队列中的是下一层的节点

https://camo.githubusercontent.com/ed6aa613989caf2c092b40817aa16569f6d8b7a7e424c13366613baf32e7655c/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f6d6178696d756d5f6c656e6774685f6f665f615f62696e6172795f747265655f312e706e67

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> results;
        if (root == nullptr) return results;

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

        while (!q.empty()) {
            int size = q.size();
            vector<int> newLevel;
            while (size-- > 0) {
                TreeNode* node = q.front();
                q.pop();
                if (node->left != nullptr) q.push(node->left);
                if (node->right != nullptr) q.push(node->right);
                newLevel.push_back(node->val);
            }
            results.push_back(newLevel);
        }
        return results;
    }
};

• Time: $O(N)$，N 是二叉树的节点总数，每个节点入列出列一次。
• Space: $O(N)$，队列中的元素不超过 N 个。