本文介绍: 给你二叉树的根节点 root ,返回其节点值的层序遍历。输入:root = [3,9,20,null,null,15,7]输出:[[3],[9,20],[15,7]]输入:root = [1]输出:[[1]]输入:root = []输出:[]树中节点数目在范围[0, 2000]内。
本文是力扣LeeCode-102、二又树的层序遍历 学习与理解过程,本文仅做学习之用,对本题感兴趣的小伙伴可以出门左拐LeeCode。
给你二叉树的根节点 root ,返回其节点值的 层序遍历
。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]
示例 2:
输入:root = [1]
输出:[[1]]
示例 3:
输入:root = []
输出:[]
提示:
树中节点数目在范围 [0, 2000]
内
-1000 <= Node.val <= 1000
思路
层序遍历
,符合队列queue
先进先出
的规律:左边先进,左边先出,只要保证从上到下每层遍历即可
代码实现
下列两段代码可以作为BFS模版
解决二叉树层序遍历相关的问题
BFS模版1
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root==null) return res;
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> tempList = new ArrayList<>();
// 这⾥⼀定要使⽤固定⼤⼩size,不要使⽤que.size(),因为que.size是不断变化的
for(int i=0;i<size;i++){
TreeNode node = queue.poll();
tempList.add(node.val);
if(node.left!=null)queue.add(node.left);
if(node.right!=null)queue.add(node.right);
}
res.add(tempList); //每层遍历完,放进结果即可
}
return res;
}
}
BFS模版2
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root==null){return res;}
int start = 0;
int end = 1;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
List<Integer> tempList = new ArrayList<>();
while(!queue.isEmpty()){
TreeNode t = queue.poll();
tempList.add(t.val);
start++;
if(t.left!=null) queue.add(t.left);
if(t.right!=null) queue.add(t.right);
if(start == end){ //某层都遍历完后,才添加结果,并初始化
res.add(new ArrayList<>(tempList));
start = 0;
end = queue.size();
tempList.clear();
}
}
return res;
}
}
最重要的一句话:做二叉树的题目,首先需要确认的是遍历顺序
大佬们有更好的方法,请不吝赐教,谢谢
原文地址:https://blog.csdn.net/kdzandlbj/article/details/135614421
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_59278.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。