NC15 求二叉树的层序遍历（四种语言+视频讲解）

1.题目描述：

2.题目链接：
https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3?tpId=188&&tqId=36551&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking

3.设计思想：
就像题目描述所说，从左到右，一层一层的遍历，即BFS遍历。
首先我们定义一个队列，然后将根节点入队，当队列不为空的时候，需要进行以下两个操作：1）求出当前队列的长度大小len 。
2）取出队列前len个节点，每取出一个节点，就把对应节点的左右孩子入队（前提孩子不为空），然后重复这一过程直到队列为空后输出结果。
详细操作流程看下图

-视频讲解链接B站视频讲解

4.代码：
c++版本:

    /**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型vector<vector<>&gt;
     */
    vector<vector<int> &gt; levelOrder(TreeNode* root) {
        vector<vector<int> &gt;res;//用于返回最后的结果
        if(root == NULL) return res;//如果根节点为空就返回结果
        queue<treenode *>q;//用于存储每一层的节点
        q.push(root);
        while(!q.empty()){
            vector<int>temp;//用于存储当前遍历这一层的节点
            int n = q.size();
            for(int i = 0;i &lt; n;i ++){
                TreeNode *node = q.front();//取出队列的第一个元素
                q.pop();
                temp.push_back(node-&gt;val);//将队头元素保存起来
                if(node-&gt;left != NULL) q.push(node-&gt;left);//左孩子如果不为空就进队列
                if(node-&gt;right != NULL) q.push(node-&gt;right);//右孩子如果不为空就进队列
            }
            res.push_back(temp);//将这一层的节点数里面据保存到res
        }
        return res;
    }

};

Java版本：

import java.util.*;
public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList<arraylist<>&gt;
     */
    public ArrayList<arraylist<integer>&gt; levelOrder (TreeNode root) {
        ArrayList<arraylist<integer>&gt; res = new ArrayList();//用于返回最后的结果
        if(root == null) return res;//如果根节点为空就返回结果
        Queue<treenode> q = new LinkedList<treenode>();//用于存储每一层的节点
        q.add(root);
        while(!q.isEmpty()){
            int n = q.size();
            ArrayList<integer> temp = new ArrayList&lt;&gt;();//用于存储当前遍历这一层的节点
            for(int i = 0;i &lt; n;i ++){
                TreeNode node = q.poll();//取出队列的第一个元素
                temp.add(node.val);//将队头元素保存起来
                if(node.left != null) q.add(node.left);//左孩子如果不为空就进队列
                if(node.right != null) q.add(node.right);//右孩子如果不为空就进队列
            }
            res.add(temp);//将这一层的节点数里面据保存到res
        }
        return res;
    }
}

Python版本:

```
import queue
class Solution:
def levelOrder(self , root ):
res = []#用于返回最后的结果
if not root:
return res#如果根节点为空就返回结果
q = queue.Queue()#用于存储每一层的节点
q.put(root)
while q.qsize() >0:
temp = []#用于存储当前遍历这一层的节点
n = q.qsize()
for i in range(n):
node = q.get()#取出队列的第一个元素
temp.append(node.val)#将队头元素保存起来
if node.left:
q.put(node.left)#左孩子如果不为空就进队列
if node.right:
q.put(node.right)#右孩子如果不为空就进队列
res.append(temp)#将这一层的节点数里面据保存到res

    return res

```</arraylist<integer></arraylist<integer></arraylist<></integer></integer></vector<int></vector<int></vector<></int></int>