题解 | #牛的层级关系# 层序遍历

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector<vector<>>
     */
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) {
            return ans;
        }
        queue<TreeNode*> qu;
        qu.push(root);
        while (!qu.empty()) {
            int size = qu.size();
            vector<int> temp;
            for (int i = 0; i < size; i++) {
                TreeNode* node = qu.front();
                qu.pop();
                temp.emplace_back(node->val);
                if (node->left) {
                    qu.push(node->left);
                }
                if (node->right) {
                    qu.push(node->right);
                }
            }
            ans.emplace_back(temp);
        }
        return ans;
    }
};

时间复杂度：O(n)，其中n为二叉树的节点数，因为我们需要遍历每个节点一次

空间复杂度：O(m)，其中m为二叉树中每一层的最大节点数。在最坏情况下，队列中会存储二叉树最底层的所有节点，因此空间复杂度为O(m)