## 题目地址

https://leetcode.com/problems/binary-tree-level-order-traversal/

## 题目描述

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree `{3,9,20,#,#,15,7}`,

``````    3
/ \
9  20
/  \
15   7
``````

return its level order traversal as:

``````[
[3],
[9,20],
[15,7]
]
``````

## 思路

``````class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> res;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
vector<int> oneLevel;
for (int i = q.size(); i > 0; --i) {
TreeNode *t = q.front(); q.pop();
oneLevel.push_back(t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
res.push_back(oneLevel);
}
return res;
}
};
``````

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

## 关键点解析

• 队列

• 队列中用Null(一个特殊元素)来划分每层

• 树的基本操作- 遍历 - 层次遍历（BFS）

• 注意塞入null的时候，判断一下当前队列是否为空，不然会无限循环

## 代码

• 语言支持：JS，C++，Python3

Javascript Code:

``````/*
* @lc app=leetcode id=102 lang=javascript
*
* [102] Binary Tree Level Order Traversal
*
* https://leetcode.com/problems/binary-tree-level-order-traversal/description/
*
* algorithms
* Medium (47.18%)
* Total Accepted:    346.4K
* Total Submissions: 731.3K
* Testcase Example:  '[3,9,20,null,null,15,7]'
*
* Given a binary tree, return the level order traversal of its nodes' values.
* (ie, from left to right, level by level).
*
*
* For example:
* Given binary tree [3,9,20,null,null,15,7],
*
*
* ⁠   3
* ⁠  / \
* ⁠ 9  20
* ⁠   /  \
* ⁠  15   7
*
*
*
* return its level order traversal as:
*
* [
* ⁠ [3],
* ⁠ [9,20],
* ⁠ [15,7]
* ]
*
*
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if (!root) return [];
const items = []; // 存放所有节点
const queue = [root, null]; // null 简化操作
let levelNodes = []; // 存放每一层的节点

while (queue.length > 0) {
const t = queue.shift();

if (t) {
levelNodes.push(t.val)
if (t.left) {
queue.push(t.left);
}
if (t.right) {
queue.push(t.right);
}
} else { // 一层已经遍历完了
items.push(levelNodes);
levelNodes = [];
if (queue.length > 0) {
queue.push(null)
}
}
}

return items;
};

``````

C++ Code:

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

// 迭代
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
auto ret = vector<vector<int>>();
if (root == nullptr) return ret;
auto q = vector<TreeNode*>();
q.push_back(root);
auto level = 0;
while (!q.empty())
{
auto sz = q.size();
ret.push_back(vector<int>());
for (auto i = 0; i < sz; ++i)
{
auto t = q.front();
q.erase(q.begin());
ret[level].push_back(t->val);
if (t->left != nullptr) q.push_back(t->left);
if (t->right != nullptr) q.push_back(t->right);
}
++level;
}
return ret;
}
};

// 递归
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> v;
levelOrder(root, 0, v);
return v;
}
private:
void levelOrder(TreeNode* root, int level, vector<vector<int>>& v) {
if (root == NULL) return;
if (v.size() < level + 1) v.resize(level + 1);
v[level].push_back(root->val);
levelOrder(root->left, level + 1, v);
levelOrder(root->right, level + 1, v);
}
};
``````

Python Code：

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
"""递归法"""
if root is None:
return []

result = []

"""递归函数
:param level int 当前在二叉树的层次
:param node TreeNode 当前节点
"""
if level > len(result) - 1:
result.append([])

result[level].append(node.val)
if node.left:
if node.right: