广州网站建设网站制作公司,protenus代做网站,做网站 赚钱多吗,韩国情侣网站模板目录 题目描述#xff1a;102. 二叉树的层序遍历#xff08;中等#xff09;题目接口解题思路代码 PS: 题目描述#xff1a;102. 二叉树的层序遍历#xff08;中等#xff09;
给你二叉树的根节点 root #xff0c;返回其节点值的 层序遍历 。 #xff08;即逐层地102. 二叉树的层序遍历中等题目接口解题思路代码 PS: 题目描述102. 二叉树的层序遍历中等
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。
LeetCode做题链接LeetCode-二叉树的层序遍历
示例 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题目接口
/*** 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 ListListInteger levelOrder(TreeNode root) {}
}解题思路
树的层序遍历可以用BFS因为层序遍历要求的输入结果和BFS是不同的。层序遍历要求我们区分每一层也就是返回一个二维数组。而BFS的遍历结果是一个一维数组无法区分每一层。
思路如下 1.创建一个空的结果列表res这个列表用于存储每一层节点的值。 2.创建一个队列queue并将根节点root加入队列。 3.当队列不为空时执行以下操作
获取当前队列的长度即当前层的节点个数。创建一个空的列表level用于存储当前层的节点值。遍历当前层的所有节点对于每个节点执行以下操作 从队列中取出一个节点并把它的值加入到列表level中。如果这个节点有左子节点那么将左子节点加入到队列中如果这个节点有右子节点那么将右子节点加入到队列中。 把列表level加入到结果列表res中。
4.最后返回结果列表res这个列表中的每个元素都是一个列表表示树的每一层的所有节点的值。
代码
/*** 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 ListListInteger levelOrder(TreeNode root) {// 创建一个二维列表用于存储每一层的节点值ListListInteger res new ArrayList();// 创建一个队列用于层序遍历QueueTreeNode queue new ArrayDeque();// 如果根节点不为空将其加入队列if (root ! null) {queue.add(root);}// 当队列不为空时进行循环while (!queue.isEmpty()) {// 获取当前层的节点个数int n queue.size();// 创建一个列表用于存储当前层的节点值ListInteger level new ArrayList();// 遍历当前层的每个节点for (int i 0; i n; i) {// 取出队首节点TreeNode node queue.poll();// 将节点值加入当前层的列表level.add(node.val);// 如果当前节点的左子节点不为空将其加入队列if (node.left ! null) {queue.add(node.left);}// 如果当前节点的右子节点不为空将其加入队列if (node.right ! null) {queue.add(node.right);}}// 将当前层的节点值列表加入结果列表res.add(level);}// 返回结果列表return res;}
}成功
PS:
感谢您的阅读如果您觉得本篇文章对您有所帮助请给予博主一个赞喔~
