二叉树层次遍历I
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]
思路:提到层次遍历,首先想到的就是用队列,首先将头节点放入队列中,然后出队,将出队节点的左节点和右节点分别入队,一直重复该操作,直到队列为空。
但是该题要求输出要求每一层放到一个List中,所以需要在原有基础上,做一些调整。通过获取队列的大小,来判断哪些节点是在同一层
解题:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root != null) {
queue.add(root);
}
while(!queue.isEmpty()) {
List<Integer> arr = new ArrayList<>();
int currenLvelSize = queue.size();
for (int i = 1; i <= currenLvelSize; i++) {
TreeNode poll = queue.poll();
arr.add(poll.val);
if(poll.left != null) {
queue.add(poll.left);
}
if(poll.right != null) {
queue.add(poll.right);
}
}
res.add(arr);
}
return res;
}
}
我最开始想到的思路就是在每一层结束的时候添加一个标记位,来表示该层的结束。实现代码如下:文章来源:https://www.toymoban.com/news/detail-812686.html
个人觉得没什么问题,但是最终力扣判定超时。不知道为啥。文章来源地址https://www.toymoban.com/news/detail-812686.html
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root != null) {
queue.add(root);
queue.add(new TreeNode(Integer.MAX_VALUE));
}
while(!queue.isEmpty()) {
List<Integer> arr = new ArrayList<>();
while (!queue.isEmpty() && queue.peek().val != Integer.MAX_VALUE) {
TreeNode poll = queue.poll();
arr.add(poll.val);
if(poll.left != null) {
queue.add(poll.left);
}
if(poll.right != null) {
queue.add(poll.right);
}
}
queue.add(new TreeNode(Integer.MAX_VALUE));
if(arr.size()>0) {
res.add(arr);
}
queue.poll();
}
return res;
}
到了这里,关于数据结构与算法-二叉树-层次遍历I的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!