二叉树的层次遍历是一个非常简单的问题，当时很多人因为都没有接触过，所以毫不准备就去面试容易临阵逃脱，本关，我们来看一下层次遍历问题。
1. 层次遍历简介
广度优先在面试中出现的频率非常高，属于简单题，但是很多人在面试的时候遇到就放弃了，实在可惜，我们本章就来研究一下到底难在哪里。
广度优先遍历又叫做层次遍历，基本过程如下：
层次遍历就是从根节点开始，先访问根节点下面一层的全部元素，再访问之后的乘车，类似金字塔一样，一层层往下访问，我们可以看到这里就是从左到右一层层地区遍历二叉树，先访问 3 ，之后访问 1 的 左右孩子 9 和 20，之后分别访问 9 和 20 的左右孩子节点【8,13】和【15,17】，最后得到的结果如下：【3,9,20,8,13,15,17】
这里的问题在于如何将遍历过后元素的子孩子节点进行保存了，例如访问 9 的时候，其左右孩子节点 8 和 13 应该先保存一下，然后直到 20 出现之后，才会进行处理，使用队列就能完美解决以上这个问题，如上面图中描述：
1. 首先 3 入队
2. 然后 3 出队，之后将 3 的左右孩子节点 9 和 20 保存到队列中
3. 之后 9 出队，将 9 的 左右孩子 8 和 13 入队
4. 之后 20 出队，将 20 的左右孩子节点 15 和 7 入队
5. 之后8,13,15,17 分别出队，此时都是叶子节点，只要出队就可以了
该过程不复杂，如果能将树的每层次分开了，能否整点新花样？首先，能否将每层的元素顺序给反转一下呢？能否奇数行不变，只将偶数行反转呢？能否将输出层次从低到root逐层输出呢？再来，既然能拿到每一层的元素了，能否找到当前层最大的元素？最小的元素？最右的元素（右视图）？最左的元素（左视图）?整个层的平均值呢？
很明显都可以！这么折腾有什么作用？没啥用！但这就是最层次遍历的高频算法题！这就是 LeetCode 里面经典的层次遍历问题：
2. 基本的层序遍历以及变换
我们先看看最简单的情况，仅仅遍历并输出全部元素，如下：
3
/
9 20
/
15 7
上面二叉树的输出结果是 【3 9 20 15 7】，方法上面已经图示了，这里来看一下怎么实现代码，先访问根节点，然后将其左右孩子放到队列里面，接着继续出队，出来的元素将其左右孩子节点放到队列里面，直到队列为空退出就可以了：
List simpleLevelOrder (TreeNode root){
if(root == null){
return new ArrayList();
}
List res = new ArrayList();
LinkedList queue = new LinkedList();
// 将根节点放入队列中，然后不断遍历序列
queue.add(root);
// 有多少元素就执行多少次
while(queue.size() > 0){
// 获取当前队列的长度，这个长度相当于当前这一层的节点个数
TreeNode t = queue.remove();
res.add(t.val);
if(t.left != null){
queue.add(t.left);
}
if(t.right != null){
queue.add(t.right);
}
}
return res;
}
}
def simple_level_order(self, root):
averages = list()
queue = collections.deque([root])
while queue:
total = 0
size = len(queue)
for _ in range(size):
node = queue.popleft()
print node.val
left, right = node.left, node.right
if left:
queue.append(left)
if right:
queue.append(right)
vector levelOrder(TreeNode* root) {
vector ret;
if (!root) {
return ret;
}
queue q;
q.push(root);
while (!q.empty()) {
int currentLevelSize = q.size();
ret.push_back(vector());
for (int i = 1; i left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return ret;
}
根据树的结构可以看到，一个结点在一层访问之后，其子孩子都是在下层按照 FIFO 的顺序处理的，因此队列就是一个缓存的作用。
如果你要将每层的元素分开，要怎么做呢？请看下一题：
2.1. 二叉树的层序遍历
LeetCode 102 题目要求：给你一个二叉树，请你返回其按层序遍历得到的节点值。(即逐层地，从左到右访问所有节点)。
二叉树：[3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]
我们再观察执行过程图，我们先将根节点放到队列中，然后不断遍历队列。
那如何判断某一层访问完了呢？简单，用一个变量size标记一下就行了，size表示某一层的元素个数，只要出队，就将size减1，减到0就说明该层元素访问完了。当size变成0之后，这时队列中剩余元素的个数恰好就是下一层元素的个数，因此重新将size标记为下一层的元素个数就可以继续处理新的一行了，例如在上面的序列中：
1.首先拿根节点3，其左/右子结点都不为空，就将其左右放入队列中，因此此时3已经出队了，剩余元素9和20恰好就是第二层的所有结点，此时size=2。
2.继续，将9从队列中拿走，size--变成1，并将其子孩子8和13入队。之后再将20 出队，并将其子孩子15和7入队，此时再次size--，变成9了。当size=0，说明当前层已经处理完了，此时队列有四个元素，而且恰好就是下一层的元素个数。
最后，我们把每层遍历到的节点都放入到一个结果集中，将其返回就可以了：
按层打印经典版代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List levelOrder(TreeNode root) {
if(root == null){
return new ArrayList();
}
List res = new ArrayList();
LinkedList queue = new LinkedList();
//将根节点放入队列中，然后不断遍历队列
queue.add(root);
while(queue.size() > 0 ){
//获取当前队列的长度，也就是当前这一层的元素个数
int size = queue.size();
ArrayList tmp = new ArrayList();
//将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
//如果节点的左/右子树不为空，也放入队列中
for(int i = 0;i < size; i++){
TreeNode t = queue.remove();
tmp.add(t.val);
if(t.left!= null){
queue.add(t.left);
}
if(t.right != null){
queue.add(t.right);
}
}
res.add(tmp);
}
return res;
}
}
vector levelOrder(TreeNode* root) {
vector ret;
if (!root) {
return ret;
}
queue q;
q.push(root);
while (!q.empty()) {
int currentLevelSize = q.size();
ret.push_back(vector());
for (int i = 1; i left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return ret;
}
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
res = []
queue = [root]
while queue:
# 获取当前队列的长度，这个长度相当于 当前这一层的节点个数
size = len(queue)
tmp = []
# 将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
# 如果节点的左/右子树不为空，也放入队列中
for _ in xrange(size):
r = queue.pop(0)
tmp.append(r.val)
if r.left:
queue.append(r.left)
if r.right:
queue.append(r.right)
# 将临时list加入最终返回结果中
res.append(tmp)
return res
上面的代码是本章最重要的算法之一，也是整个算法体系的核心算法之一，与链表反转、二分查找属于同一个级别，务必认真学习！理解透彻，然后记住！
上面的算法理解了，那接下来一些列的问题就轻松搞定了。
注意
另外一个需要注意的是在java中实现队列的方法基础类不止一个，对于C++ 和Python等都有类似的情况，我们要有意识的记住这些用法。
2.2. 层序遍历——自底向上
LeetCode 107.给定一个二叉树，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。例如给定的二叉树为：
返回结果为：
[
[15,7],
[9,20],
[3]
]
如果要求从上到下输出每一层的节点值，做法是很直观的，在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的尾部。这道题要求从下到上输出每一层的节点值，只要对上述操作稍作修改即可，在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的头部。
为了降低在结果列表的头部添加一层节点值的列表的时间复杂度，结果列表可以使用链表的结构，在链表头部添加一层节点值的列表的时间复杂度是 O(1)。在 Java 中，由于我们需要返回的 List 是一个接口，这里可以使用链表实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List levelOrderBottom(TreeNode root) {
if(root == null){
return new LinkedList();
}
List levelOrder = new LinkedList();
Queue queue = new LinkedList();
queue.offer(root);
while(queue.size() > 0){
List level = new ArrayList();
int size = queue.size();
for(int i = 0; i< size;i++){
TreeNode node = queue.poll();
level.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
levelOrder.add(0,level);// 栈
}
return levelOrder;
}
}
在C++版本，注意vector 这种定义，后面的>>之间要有空格 ，否则会报错
vector levelOrderBottom(TreeNode *root)
{
auto levelOrder = vector();
if (!root)
{
return levelOrder;
}
queue q;
q.push(root);
while (!q.empty())
{
auto level = vector();
int size = q.size();
for (int i = 0; i val);
if (node->left)
{
q.push(node->left);
}
if (node->right)
{
q.push(node->right);
}
}
levelOrder.push_back(level);
}
reverse(levelOrder.begin(), levelOrder.end());
return levelOrder;
}
def levelOrderBottom(self, root) :
levelOrder = list()
if not root:
return levelOrder
q = collections.deque([root])
while q:
level = list()
size = len(q)
for _ in range(size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
levelOrder.append(level)
return levelOrder[::-1]
2.3. 二叉树的锯齿形层序遍历
LeetCode103 题，要求是：给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：给定二叉树 [3,9,20,null,null,15,7]
返回结果是：
[
[3],
[20,9],
[15,7]
]
这个题也是102的变种，只是最后输出的要求有所变化，要求我们按层数的奇偶来决定每一层的输出顺序。如果当前层数是偶数，从左至右输出当前层的节点值，否则，从右至左输出当前层的节点值。这里只要采用以
我们依然可以沿用第 102 题的思想，为了满足题目要求的返回值为「先从左往右，再从右往左」交替输出的锯齿形，可以利用「双端队列」的数据结构来维护当前层节点值输出的顺序。双端队列是一个可以在队列任意一端插入元素的队列。在广度优先搜索遍历当前层节点拓展下一层节点的时候我们仍然从左往右按顺序拓展，但是对当前层节点的存储我们维护一个变量 isOrderLeft 记录是从左至右还是从右至左的：
● 如果从左至右，我们每次将被遍历到的元素插入至双端队列的末尾。
● 从右至左，我们每次将被遍历到的元素插入至双端队列的头部。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List zigzagLevelOrder(TreeNode root) {
if(root == null){
return new LinkedList();
}
List res = new LinkedList();
Queue queue = new LinkedList();
queue.offer(root);
boolean isOrderLeft = true;
while(!queue.isEmpty()){
Deque levelList = new LinkedList();
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode curnode = queue.poll();
if(isOrderLeft){
levelList.offerLast(curnode.val);
}else{
levelList.offerFirst(curnode.val);
}
if(curnode.left != null){
queue.offer(curnode.left);
}
if(curnode.right != null){
queue.offer(curnode.right);
}
}
res.add(new LinkedList(levelList));
isOrderLeft = !isOrderLeft;
}
return res;
}
}
vector zigzagLevelOrder(TreeNode* root) {
vector ans;
if (!root) return ans;
deque que;
que.push_back(root);
bool zigzag = true;
TreeNode* tmp;
while (!que.empty()) {
int Size = que.size();
vector tmp_vec;
while (Size) {
if (zigzag) { // 前取后放
tmp = que.front();
que.pop_front();
if (tmp->left) que.push_back(tmp->left);
if (tmp->right) que.push_back(tmp->right);
} else { //后取前放
tmp = que.back();
que.pop_back();
if (tmp->right) que.push_front(tmp->right);
if (tmp->left) que.push_front(tmp->left);
}
tmp_vec.push_back(tmp->val);
--Size;
}
zigzag = !zigzag;
ans.push_back(tmp_vec);
}
return ans;
}
def zigzagLevelOrder(self, root) :
if not root:
return []
res = []
q = collections.deque()
q.append(root)
while q:
res_tmp = []
n = len(q)
for i in range(n):
tmp = q.popleft()
res_tmp.append(tmp.val)
if tmp.left:
q.append(tmp.left)
if tmp.right:
q.append(tmp.right)
res.append(res_tmp)
for j in range(len(res)):
if j % 2 == 1:
res[j].reverse()
return res
2.4. N叉树的层序遍历
LeetCode429 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
输入：root = [1,null,3,2,4,null,5,6](表述树的元素是这个序列)
输出：[[1],[3,2,4],[5,6]]
N叉树的定义如下，就是一个值，加一个列表，其类型仍然是Node：
class Node {
public int val;
public List children;
}
这个也是102的扩展，很简单的广度优先，与二叉树的层序遍历基本一样，借助队列即可实现。
/*
// Definition for a Node.
class Node {
public int val;
public List children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List levelOrder(Node root) {
if(root == null){
return new ArrayList();
}
List res = new ArrayList();
Queuequeue = new ArrayDeque();
queue.offer(root);
while(!queue.isEmpty()){
int n = queue.size();
List level = new ArrayList();
for(int i = 0; i < n;i++){
Node cur = queue.poll();
level.add(cur.val);
for(Node child:cur.children){
queue.offer(child);
}
}
res.add(level);
}
return res;
}
}
vector levelOrder(Node* root) {
if (!root) {
return {};
}
vector ans;
queue q;
q.push(root);
while (!q.empty()) {
int cnt = q.size();
vector level;
for (int i = 0; i val);
for (Node* child: cur->children) {
q.push(child);
}
}
ans.push_back(move(level));
}
return ans;
}
class Solution:
def levelOrder(self, root: 'Node'):
if not root:
return []
ans = list()
q = deque([root])
while q:
cnt = len(q)
level = list()
for _ in range(cnt):
cur = q.popleft()
level.append(cur.val)
for child in cur.children:
q.append(child)
ans.append(level)
return ans
3. 几个处理每层元素的题目
如果我们拿到了每一层的元素，那是不是可以利用一下造几个题呢？例如每层找最大值、平均值、最右侧的值呢？当然可以。LeetCode里就有三道非常明显的题目。
515.在每个树行中找最大值(最小)
637.二叉树的层平均值
199.二叉树的右视图
既然能这么干，我们能否自己造几个题：求每层最小值可以不？求每层最左侧的可以不？我们是不是可以给LeetCode贡献几道题了？
3.1. 在每个树行中找最大值
LeetCode 515题目要求：给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
这里其实就是在得到一层之后使用一个变量来记录当前得到的最大值：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List largestValues(TreeNode root) {
if(root == null){
return new ArrayList();
}
List res = new ArrayList();
Deque deque = new ArrayDeque();
deque.add(root);
while(!deque.isEmpty()){
int size = deque.size();
int levelMaxNum = Integer.MIN_VALUE;
for (int i = 0; i < size; i++) {
TreeNode node = deque.poll();
levelMaxNum = Math.max(node.val,levelMaxNum);
if (node.left != null) deque.addLast(node.left);
if (node.right != null) deque.addLast(node.right);
}
res.add(levelMaxNum);
}
return res;
}
}
def largestValues(self, root):
if root is None:
return []
ans = []
q = [root]
while q:
maxVal = -inf
tmp = q
q = []
for node in tmp:
maxVal = max(maxVal, node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(maxVal)
return ans
vector largestValues(TreeNode* root) {
if (!root) {
return {};
}
vector res;
queue q;
q.push(root);
while (!q.empty()) {
int len = q.size();
int maxVal = INT_MIN;
while (len > 0) {
len--;
auto t = q.front();
q.pop();
maxVal = max(maxVal, t->val);
if (t->left) {
q.push(t->left);
}
if (t->right) {
q.push(t->right);
}
}
res.push_back(maxVal);
}
return res;
}
3.2. 在每个树行中找平均值
LeetCode 637 要求给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。示例
这个题和前面的几个一样，只不过是每层都先将元素保存下来，最后求平均就行了：
public List averageOfLevels(TreeNode root) {
List res = new ArrayList();
if (root == null) return res;
Queue list = new LinkedList();
list.add(root);
while (list.size() != 0){
int len = list.size();
double sum = 0;
for (int i = 0; i < len; i++){
TreeNode node = list.poll();
sum += node.val;
if (node.left != null) list.add(node.left);
if (node.right != null) list.add(node.right);
}
res.add(sum/len);
}
return res;
}
class Solution {
public:
vector averageOfLevels(TreeNode* root) {
auto averages = vector();
auto q = queue();
q.push(root);
while (!q.empty()) {
double sum = 0;
int size = q.size();
for (int i = 0; i val;
auto left = node->left, right = node->right;
if (left != nullptr) {
q.push(left);
}
if (right != nullptr) {
q.push(right);
}
}
averages.push_back(sum / size);
}
return averages;
}
};
class Solution:
def largestValues(self, root):
if root is None:
return []
ans = []
q = [root]
while q:
maxVal = -inf
tmp = q
q = []
for node in tmp:
maxVal = max(maxVal, node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(maxVal)
return ans
3.3. 二叉树的右视图
LeetCode 199题目要求是：给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。例如：
这个题目出现频率还挺高的，如果没有提前思考过，面试现场可能会想不到怎么做。其实也很简单那，利用 BFS 进行层次遍历，记录下每层的最后一个元素。
public List rightSideView(TreeNode root) {
List res = new ArrayList();
if (root == null) {
return res;
}
Queue queue = new LinkedList();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (i == size - 1) { //将当前层的最后一个节点放入结果列表
res.add(node.val);
}
}
}
return res;
}
def rightSideView(self, root):
rightmost_value_at_depth = dict() # 深度为索引，存放节点的值
max_depth = -1
queue = deque([(root, 0)])
while queue:
node, depth = queue.popleft()
if node is not None:
# 维护二叉树的最大深度
max_depth = max(max_depth, depth)
# 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
rightmost_value_at_depth[depth] = node.val
queue.append((node.left, depth + 1))
queue.append((node.right, depth + 1))
return [rightmost_value_at_depth[depth] for depth in range(max_depth + 1)]
vector rightSideView(TreeNode* root) {
vector res;
if (root == NULL) {
return res;
}
queue q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i left != NULL) {
q.push(node->left);
}
if (node->right != NULL) {
q.push(node->right);
}
if (i == size - 1) { // 将当前层的最后一个节点放入结果列表
res.push_back(node->val);
}
}
}
return res;
}
是不是很简单，这三题本质都是层次遍历的变形。
我们来造题：如果将右视图换成左视图呢？请读者自行思考。
再思考，俯视图行不行？答案是不行的，那为什么不行呢，请读者思考。
3.4. 最底层最左边
上面这个层次遍历的思想可以方便的解决，LeetCode513. 二叉树最底层最左边的值的问题：给定一个二叉树的 根节点root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例1：
输入: root = [2,1,3]
输出: 1
示例2：
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
我们在第二章介绍了很多次如何使用层次遍历，这里有两个问题：该怎么知道什么时候到了最底层呢？假如最底层有两个，该怎么知道哪个是最左的呢？
我们继续观察层次遍历的执行过程：
我们可以发现，正常执行层次遍历，不管最底层有几个元素，最后一个输出的一定是是最底层最右的元素7，那这里我们就想了，能否将该处理与上一次题的翻转结合一下，每一层都是先反转再放入队列，就可以让最后一个输出的是最左的呢？是的，这就是解决本题的关键。
public int findBottomLeftValue(TreeNode root) {
if (root.left == null && root.right == null) {
return root.val;
}
Queue queue = new LinkedList();
queue.offer(root);
TreeNode temp = new TreeNode(-100);
while (!queue.isEmpty()) {
temp = queue.poll();
if (temp.right != null) {
// 先把右节点加入 queue
queue.offer(temp.right);
}
if (temp.left != null) {
// 再把左节点加入 queue
queue.offer(temp.left);
}
}
return temp.val;
}
class Solution:
def findBottomLeftValue(self, root: ) :
curVal = curHeight = 0
def dfs(node: , height) :
if node is None:
return
height += 1
dfs(node.left, height)
dfs(node.right, height)
nonlocal curVal, curHeight
if height > curHeight:
curHeight = height
curVal = node.val
dfs(root, 0)
return curVal
int findBottomLeftValue(TreeNode* root) {
if (root == nullptr || root->left == nullptr && root->right == nullptr) {
return root->val;
}
Queue queue;
queue.push(root);
TreeNode* temp = new TreeNode(-100);
while (!queue.empty()) {
temp = queue.front();
queue.pop();
if (temp->right != nullptr) {
queue.push(temp->right);
}
if (temp->left != nullptr) {
queue.push(temp->left);
}
}
return temp->val;
}
本关我们分析了很多题目，研究的时候你会发现所有的题目都是来自几种遍历的拓展，只不过结束条件和处理方式存在区别，除此之外还有一些质量不错的二叉树的题目，例如LeetCode404.计算给定二叉树的所有左叶子之和等等，感兴趣的同学可以研究一下。
4. 通关文牒
本关讲解了层次遍历的问题，掌握这几道题，基本就不用怕层次遍历的问题了。
