欢迎大家来到IT世界,在知识的湖畔探索吧!
#头条创作挑战赛#
3妹:2哥2哥,你猜今天我在公交车上看到了什么。
2哥:什么啊,跟我说说,我这颗八卦好奇心。
3妹:我听到2个人在讨论他们的工资,一个人说他的多次只有****, 另一个人说他更惨,工资更少,只有****。
2哥:这有什么好稀奇的,我还以为是什么呢?
3妹:你不知道,我发现人与人的工资差别还是很大的。
2哥:那当然了,每个人的能力不一样,收入也自然不一样。 还有,这个社会也只能相对公平,并非绝对公平。
3妹:哎,什么时候老板能给我涨工资啊。
2哥:哈哈哈哈, 来我们先刷刷算法题吧。
题目:
给你二叉树的根节点 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
思路:
与树的前、中、后序遍历的DFS思想不同,层次遍历用到的是BFS思想。一般DFS用递归去实现(也可以用栈实现),BFS需要用队列去实现。
层次遍历的步骤是:
1.对于不为空的结点,先把该结点加入到队列中
2.从队中拿出结点,如果该结点的左右结点不为空,就分别把左右结点加入到队列中
3.重复以上操作直到队列为空
java代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (root == null) {
return res;
}
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
list.add(root);
while (!list.isEmpty()) {
int size = list.size();
List<Integer> subList = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode cur = list.poll();
subList.add(cur.val);
if (cur.left != null) {
list.add(cur.left);
}
if (cur.right != null) {
list.add(cur.right);
}
}
res.add(subList);
}
return res;
}
}
欢迎大家来到IT世界,在知识的湖畔探索吧!
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/21965.html