第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0102. 二叉树的层序遍历

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

题目描述

1
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
2
3
4
5
示例:
6
二叉树:[3,9,20,null,null,15,7],
7
8
3
9
/ \
10
9 20
11
/ \
12
15 7
13
返回其层次遍历结果:
14
15
[
16
[3],
17
[9,20],
18
[15,7]
19
]
Copied!

前置知识

  • 队列

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这是一个典型的二叉树遍历问题, 关于二叉树遍历,我总结了一个专题,大家可以先去看下那个,然后再来刷这道题。
这道题可以借助队列实现,首先把 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:
1
/**
2
* @param {TreeNode} root
3
* @return {number[][]}
4
*/
5
var levelOrder = function (root) {
6
if (!root) return [];
7
const items = []; // 存放所有节点
8
const queue = [root, null]; // null 简化操作
9
let levelNodes = []; // 存放每一层的节点
10
11
while (queue.length > 0) {
12
const t = queue.shift();
13
14
if (t) {
15
levelNodes.push(t.val);
16
if (t.left) {
17
queue.push(t.left);
18
}
19
if (t.right) {
20
queue.push(t.right);
21
}
22
} else {
23
// 一层已经遍历完了
24
items.push(levelNodes);
25
levelNodes = [];
26
if (queue.length > 0) {
27
queue.push(null);
28
}
29
}
30
}
31
32
return items;
33
};
Copied!
C++ Code:
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
11
// 迭代
12
class Solution {
13
public:
14
vector<vector<int>> levelOrder(TreeNode* root) {
15
auto ret = vector<vector<int>>();
16
if (root == nullptr) return ret;
17
auto q = vector<TreeNode*>();
18
q.push_back(root);
19
auto level = 0;
20
while (!q.empty())
21
{
22
auto sz = q.size();
23
ret.push_back(vector<int>());
24
for (auto i = 0; i < sz; ++i)
25
{
26
auto t = q.front();
27
q.erase(q.begin());
28
ret[level].push_back(t->val);
29
if (t->left != nullptr) q.push_back(t->left);
30
if (t->right != nullptr) q.push_back(t->right);
31
}
32
++level;
33
}
34
return ret;
35
}
36
};
37
38
// 递归
39
class Solution {
40
public:
41
vector<vector<int>> levelOrder(TreeNode* root) {
42
vector<vector<int>> v;
43
levelOrder(root, 0, v);
44
return v;
45
}
46
private:
47
void levelOrder(TreeNode* root, int level, vector<vector<int>>& v) {
48
if (root == NULL) return;
49
if (v.size() < level + 1) v.resize(level + 1);
50
v[level].push_back(root->val);
51
levelOrder(root->left, level + 1, v);
52
levelOrder(root->right, level + 1, v);
53
}
54
};
Copied!
Python Code:
1
# Definition for a binary tree node.
2
# class TreeNode:
3
# def __init__(self, x):
4
# self.val = x
5
# self.left = None
6
# self.right = None
7
8
class Solution:
9
def levelOrder(self, root: TreeNode) -> List[List[int]]:
10
"""递归法"""
11
if root is None:
12
return []
13
14
result = []
15
16
def add_to_result(level, node):
17
"""递归函数
18
:param level int 当前在二叉树的层次
19
:param node TreeNode 当前节点
20
"""
21
if level > len(result) - 1:
22
result.append([])
23
24
result[level].append(node.val)
25
if node.left:
26
add_to_result(level+1, node.left)
27
if node.right:
28
add_to_result(level+1, node.right)
29
30
add_to_result(0, root)
31
return result
Copied!
复杂度分析
  • 时间复杂度:$O(N)$,其中 N 为树中节点总数。
  • 空间复杂度:$O(N)$,其中 N 为树中节点总数。
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 30K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。

扩展

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

相关题目

相关专题