涟源网站设计,wordpress短代码大全,天津小型企业网站设计,wordpress后台密码默认有LeetCode交流群/华为OD考试扣扣交流群可加#xff1a;948025485 可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题 绿色聊天软件戳 od1336了解算法冲刺训练 文章目录 题目链接题目描述解题思路DFS和BFS异同用队列维护的BFS 代码PythonJavaC时空复杂度 相关习题华为OD算法/大… 有LeetCode交流群/华为OD考试扣扣交流群可加948025485 可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题 绿色聊天软件戳 od1336了解算法冲刺训练 文章目录 题目链接题目描述解题思路DFS和BFS异同用队列维护的BFS 代码PythonJavaC时空复杂度 相关习题华为OD算法/大厂面试高频题算法练习冲刺训练 题目链接
LeetCode107、二叉树的层序遍历II
题目描述
给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历
示例 1 输入root [3,9,20,null,null,15,7] 输出[[[15,7],[9,20],[3]]
示例 2
输入root [1] 输出[[1]]
示例 3
输入root [] 输出[]
提示
树中节点数目在范围 [0, 2000] 内-1000 Node.val 1000
解题思路
DFS和BFS异同
二叉树层序遍历是一个非常经典的问题属于必须掌握的题目。
所谓二叉树遍历traversal指的是按照一定次序系统地访问一棵二叉树使每个节点恰好被访问一次。
二叉树遍历实质上是二叉树的线性化将树状结构变为线性结构。
二叉树遍历有两大类
深度优先depth first traversalDFS先完成一棵子树的遍历再完成另一棵广度优先breath first traversalBFS先完成一层节点的遍历再完成下一层
DFS和BFS均为树/图的搜索方式能够访问树/图中的所有节点。它们的特点可以从以下的比喻看出区别
DFS优先移动节点当对给定节点尝试过每一种可能性之后才退到前一节点来尝试下一个位置。就像一个搜索者尽可能地深入调查未知的地域直到遇到死胡同才回头。下图以前序遍历为例 BFS优先对给定节点的下一个位置进行进行尝试当对给定节点尝试过每一种可能性之后才移动到下一个节点。就像一只搜索军队铺展开来覆盖领土直到覆盖了所有地域。 用队列维护的BFS
树的广度优先遍历亦可称为层序遍历。其核心特点为从上到下、从左到右访问树中的节点每一层的节点都按顺序出现。 本题就是二叉树BFS的板子题必须掌握。
BFS通常需要通过维护一个先进先出 First In First OutFIFO) 的队列来实现。 我们需要构建一个队列q用于储存每一层的所有节点然后执行while循环循环不变量为q不为空
获得当前队列长度qSize为该层的节点个数初始化一个空的子列表subList用于储存二叉树该层所有节点的值执行for循环循环qSize次。每一次循环包含以下环节 a. 令队列q的队头节点出队记为node并将其值node.val存入subList中 b. 若node的左孩子node.left存在则令node.left从队尾入队 c. 若node的右孩子node.right存在则令node.right从队尾入队 这些后入队的节点会在下一层的遍历中被取出经过qSize次循环后subList已经储存了这一层节点的所有值将subList加入全局的答案变量ans中
这样就就是二叉树BFS的基本过程其中第3步是最关键的步骤。
如果题目有明显地要求区分每一层的情况比如本题要求每一层的节点值需要单独储存在一个子列表中则循环qSize次这个步骤是必要的。
本题沿用了LeetCode102、二叉树的层序遍历的大体框架但最后要求返回的结果是自底向上的层序遍历只需要返回ans数组的反转即可。即
return ans[::-1] 代码
Python
from collections import deque
class Solution:def levelOrder(self, root: TreeNode) - List[List[int]]:if not root: # 若根节点为空返回一个空列表return []ans list() # 初始化答案列表q deque() # 维护一个队列用于BFS过程q.append(root) # 初始化队列加入根节点while(len(q) ! 0): # 循环遍历进行BFS退出循环的条件是队列为空qSize len(q) # 获得当前队列的长度为二叉树该层节点数subList list() # 初始化子列表用于储存二叉树该层节点的值for i in range(qSize): # 循环qSize次遍历该层的节点node q.popleft() # 令队头的节点node出队subList.append(node.val) # 将node的值加入子列表中if node.left: # 若node的左节点存在入队q.append(node.left)if node.right: # 若node的右节点存在入队q.append(node.right)ans.append(subList) # 经过循环qSize次后将子列表加入答案列表return ans[::-1] # 退出while循环返回答案列表Java
class Solution {public ListListInteger levelOrderBottom(TreeNode root) {ListListInteger ans new ArrayList();if (root null) {return ans;}QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {int size queue.size();ListInteger subList new ArrayList();for (int i 0; i size; i) {TreeNode node queue.poll();subList.add(node.val);if (node.left ! null) {queue.offer(node.left);}if (node.right ! null) {queue.offer(node.right);}}ans.add(0, subList);}return ans;}
}C
class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {vectorvectorint ans;if (root nullptr) {return ans;}queueTreeNode* q;q.push(root);while (!q.empty()) {int size q.size();vectorint subList;for (int i 0; i size; i) {TreeNode* node q.front();q.pop();subList.push_back(node-val);if (node-left ! nullptr) {q.push(node-left);}if (node-right ! nullptr) {q.push(node-right);}}ans.insert(ans.begin(), subList);}return ans;}
};时空复杂度
时间复杂度O(N)。仅需一次遍历整棵树。
空间复杂度O(M)。M为层的最大节点数队列所占空间。
相关习题
LeetCode101、对称二叉树
LeetCode102、二叉树的层序遍历
LeetCode103、二叉树的锯齿形层序遍历
LeetCode107、二叉树的层序遍历II
LeetCode199、二叉树的右视图
LeetCode429、N叉树的层序遍历
LeetCode513、找树左下角的值
LeetCode515、在每个树行中找最大值
LeetCode637、二叉树的层平均值
LeetCode655、输出二叉树
LeetCode662、二叉树的最大宽度
LeetCode993、二叉树的堂兄弟节点
LeetCode1161、最大层内元素和
LeetCode1302、层数最深叶子节点的和
LeetCode1609、奇偶树 华为OD算法/大厂面试高频题算法练习冲刺训练 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名目前已服务100同学成功上岸 课程讲师为全网50w粉丝编程博主吴师兄学算法 以及小红书头部编程博主闭着眼睛学数理化 每期人数维持在20人内保证能够最大限度地满足到每一个同学的需求达到和1v1同样的学习效果 60天陪伴式学习40直播课时300动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
