题目描述
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
难度:Middle
前置知识
- 队列
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
这是一个典型的二叉树遍历问题, 关于二叉树遍历,我总结了一个专题,大家可以先去看下那个,然后再来刷这道题。
这道题可以借助队列
实现,首先把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中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
* @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:
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
* 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 = []
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为树中节点总数。
扩展
实际上这道题方法很多, 比如经典的三色标记法。
相关题目
- 103.binary-tree-zigzag-level-order-traversal
- 104.maximum-depth-of-binary-tree
-
原题leetcode链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
更多题解可以访问我的 JS中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com