## 题目地址
https://leetcode.com/problems/binary-tree-level-order-traversal/description/

## 题目描述
```
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

 

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

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

## 思路

这是一个典型的二叉树遍历问题， 关于二叉树遍历，我总结了一个[专题](https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-tree-traversal.md)，大家可以先去看下那个，然后再来刷这道题。

这道题可以借助`队列`实现，首先把root入队，然后入队一个特殊元素Null(来表示每层的结束)。


然后就是while(queue.length), 每次处理一个节点，都将其子节点（在这里是left和right）放到队列中。

然后不断的出队， 如果出队的是null，则表式这一层已经结束了，我们就继续push一个null。

如果不入队特殊元素Null来表示每层的结束，则在while循环开始时保存当前队列的长度，以保证每次只遍历一层（参考下面的C++ Code）。

> 如果采用递归方式，则需要将当前节点，当前所在的level以及结果数组传递给递归函数。在递归函数中，取出节点的值，添加到level参数对应结果数组元素中（参考下面的C++ Code 或 Python Code）。


## 关键点解析

- 队列

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

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

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


## 代码
* 语言支持：JS，C++，Python3

Javascript Code:
```js
/*
 * @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:
```C++
/**
 * 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：
```python
# 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 = []
        
        def add_to_result(level, node):
            """递归函数
            :param level int 当前在二叉树的层次
            :param node TreeNode 当前节点
            """
            if level > len(result) - 1:
                result.append([])
                
            result[level].append(node.val)
            if node.left:
                add_to_result(level+1, node.left)
            if node.right:
                add_to_result(level+1, node.right)
        
        add_to_result(0, root)
        return result
```

***复杂度分析***
- 时间复杂度：$O(N)$，其中N为树中节点总数。
- 空间复杂度：$O(N)$，其中N为树中节点总数。

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode  。 目前已经30K star啦。

大家也可以关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解

## 扩展

实际上这道题方法很多， 比如经典的三色标记法。

## 相关题目
- [103.binary-tree-zigzag-level-order-traversal](./103.binary-tree-zigzag-level-order-traversal.md)
- [104.maximum-depth-of-binary-tree](./104.maximum-depth-of-binary-tree.md)