# 0102. 二叉树的层序遍历

## 题目地址(102. 二叉树的层序遍历)

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

## 题目描述

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



示例：
二叉树：[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:

```javascript
/**
 * @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:

```cpp
/**
 * 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 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

## 扩展

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

## 相关题目

* [103.binary-tree-zigzag-level-order-traversal](/leetcode-solution/medium/103.binary-tree-zigzag-level-order-traversal.md)
* [104.maximum-depth-of-binary-tree](/leetcode-solution/easy/104.maximum-depth-of-binary-tree.md)

## 相关专题

* [二叉树的遍历](https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-tree-traversal.md)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/102.binary-tree-level-order-traversal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.