LeetCode:102.Binary Tree Level Order Traversal
程序员文章站
2024-02-19 13:54:22
...
题目要求如下:
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
大体的意思就是给你一个二叉树,用层次遍历的形式返回此二叉树。
一.我的解法
因为是要用层级遍历的形式返回二叉树,所以自然而然地想到了层级遍历,要注意每次遍历完一层后,要更新下每层结点的数量。时间复杂度是O(n),同时空间复杂度也是O(n)。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res=new ArrayList<>();
Queue<TreeNode> queue=new LinkedList<>();
int len=0;
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> ls=new ArrayList<>();
len=queue.size();
for(int i=0;i<len;i++){
TreeNode node=queue.poll();
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
ls.add(node.val);
}
res.add(new ArrayList<Integer>(ls));
}
return res;
}
}
二 .扩展
参考了一下LeetCode的讨论区的其他解法,发现除了利用BFS还可以用DFS去解决这个问题。好处是在空间减少了需要维护的队列,虽然时间复杂度上跟用BFS差不多。原理上就是先序遍历检查是否有下一层(即当前的结点子树不为空且当前的列表的子列表数目(代表目前已遍历过的层级)也小于height),有就继续进行下一层的先序遍历,没有则在同层级进行遍历。
这是原地址:https://discuss.leetcode.com/topic/4894/one-of-c-solutions-preorder
class Solution{
List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root){
preorder(root,0);
return res;
}
public void preorder(TreeNode root,int height){
if(root==null) return;
if(height>=res.size()){
res.add(new ArrayList<Integer>());
}
res.get(height).add(root.val);
preorder(root.left,height+1);
preorder(root.right,height+1);
}
}
我还是个菜鸟,如果有什么错误的地方或者想提的意见都可以评论,我会积极改进和吸收。
推荐阅读
-
LeetCode:102.Binary Tree Level Order Traversal
-
leecode每日一题01- Binary Tree Level Order Traversal [Medium]
-
LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
-
leetcode 随笔 Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode-102. Binary Tree Level Order Traversal(层次遍历保存)
-
Binary Tree Level Order Traversal LeetCode
-
LeetCode(106)Construct Binary Tree from Inorder and Postorder Traversal
-
leetcode: binary-tree-postorder-traversal:后序遍历二叉树
-
LeetCode 94. Binary Tree Inorder Traversal