solution.md

# 二叉树的层序遍历

<p>给你一个二叉树，请你返回其按 <strong>层序遍历</strong> 得到的节点值。 （即逐层地，从左到右访问所有节点）。</p>

<p> </p>

<p><strong>示例：</strong><br />
二叉树：<code>[3,9,20,null,null,15,7]</code>,</p>

<pre>
    3
   / \
  9  20
    /  \
   15   7
</pre>

<p>返回其层序遍历结果：</p>

<pre>
[
  [3],
  [9,20],
  [15,7]
]
</pre>

<p>以下<font color="red">错误</font>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;

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) {}
};
```
### after

```cpp

```

## 答案

```cpp
class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> res;

        queue<TreeNode *> q;
        if (root != NULL)
        {
            while (!q.empty())
            {
                int size = q.size();
                vector<int> temp;
                for (int i = 0; i < size; i++)
                {
                    TreeNode *t = q.front();
                    q.pop();
                    temp.push_back(t->val);
                    if (t->left != NULL)
                        q.push(t->left);
                    if (t->right != NULL)
                        q.push(t->right);
                }
                res.push_back(temp);
                temp.clear();
            }
        }
        return res;
    }
};
```
## 选项

### A
```cpp
class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> ret;
        if (!root)
            return ret;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty())
        {

            int currNodeSize = q.size();

            ret.push_back(vector<int>());

            for (int i = 1; i <= currNodeSize; i++)
            {
                TreeNode *node = q.front();
                q.pop();

                ret.back().push_back(node->val);

                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
        }
        return ret;
    }
};
```

### B
```cpp

class Solution
{
public:
    int depth(TreeNode *root)
    {
        if (root == NULL)
            return 0;
        return max(depth(root->left), depth(root->right)) + 1;
    }
    void levelOrder(vector<vector<int>> &ans, TreeNode *node, int level)
    {
        if (!node)
            return;
        ans[level].push_back(node->val);
        levelOrder(ans, node->left, level - 1);
        levelOrder(ans, node->right, level - 1);
    }
    vector<vector<int>> levelOrderBottom(TreeNode *root)
    {
        int d = depth(root);
        vector<vector<int>> ans(d, vector<int>{});
        levelOrder(ans, root, d - 1);
        return ans;
    }
};
```

### C
```cpp
class Solution
{
public:
    void dfs(TreeNode *root, vector<vector<int>> &res)
    {
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty())
        {
            int sz = q.size();
            vector<int> tp;
            while (sz > 0)
            {
                TreeNode *p = q.front();
                q.pop();
                if (p->left != NULL)
                {
                    q.push(p->left);
                }
                if (p->right != NULL)
                {
                    q.push(p->right);
                }
                tp.push_back(p->val);
                sz--;
            }
            res.push_back(tp);
        }
    }
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> res;
        if (root == NULL)
        {
            return res;
        }
        dfs(root, res);
        return res;
    }
};
```