惠阳网站制作公司,找设计工作哪个网站好,一键提取app源码,大埔县住房和城乡规划建设局网站文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;N 叉树的层序遍历
出处#xff1a;429. N 叉树的层序遍历
难度
4 级
题目描述
要求
给定一个 N 叉树的根结点 root \texttt{root} root#xf… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题N 叉树的层序遍历
出处429. N 叉树的层序遍历
难度
4 级
题目描述
要求
给定一个 N 叉树的根结点 root \texttt{root} root返回其结点值的层序遍历。
N 叉树在输入中按层序遍历序列化表示每组子结点由空值 null \texttt{null} null 分隔请参见示例。
示例
示例 1 输入 root [1,null,3,2,4,null,5,6] \texttt{root [1,null,3,2,4,null,5,6]} root [1,null,3,2,4,null,5,6] 输出 [[1],[3,2,4],[5,6]] \texttt{[[1],[3,2,4],[5,6]]} [[1],[3,2,4],[5,6]]
示例 2 输入 root [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] \texttt{root [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]} root [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出 [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]] \texttt{[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]} [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
数据范围
树中结点数目在范围 [0, 10 4 ] \texttt{[0, 10}^\texttt{4}\texttt{]} [0, 104] 内N 叉树的高度小于或等于 1000 \texttt{1000} 1000
解法
思路和算法
层序遍历的方法为从根结点开始依次遍历每一层的结点由于每一层与根结点的距离依次递增因此可以使用广度优先搜索实现层序遍历。
广度优先搜索需要使用队列存储待访问的结点初始时将根结点入队列。每次将一个结点出队列然后将该结点的子结点入队列直到队列为空时遍历结束。
由于这道题需要将结点值按照不同层分组因此需要区分不同结点所在的层确保每一轮访问的结点为同一层的全部结点。
初始时队列内只有根结点是同一层的全部结点。每一轮访问结点之前需要首先得到队列内的元素个数此时队列内的元素为同一层的全部结点然后访问这些结点并将这些结点的子结点入队列。一轮访问结束之后当前层的全部结点都已经出队列并被访问此时队列内的元素为下一层的全部结点下一轮访问时即可访问下一层的全部结点。使用上述做法可以确保每一轮访问的结点为同一层的全部结点。
对于每一层维护一个结点值序列。遍历完每一层结点之后将该层结点值序列添加到层序遍历序列中。
代码
class Solution {public ListListInteger levelOrder(Node root) {ListListInteger levelOrderTraversal new ArrayListListInteger();if (root null) {return levelOrderTraversal;}QueueNode queue new ArrayDequeNode();queue.offer(root);while (!queue.isEmpty()) {ListInteger levelValues new ArrayListInteger();int size queue.size();for (int i 0; i size; i) {Node node queue.poll();ListNode children node.children;levelValues.add(node.val);for (Node child : children) {queue.offer(child);}}levelOrderTraversal.add(levelValues);}return levelOrderTraversal;}
}复杂度分析 时间复杂度 O ( m ) O(m) O(m)其中 m m m 是二叉树的结点数。每个结点都被访问一次。 空间复杂度 O ( m ) O(m) O(m)其中 m m m 是二叉树的结点数。空间复杂度主要是队列空间队列内元素个数不超过 m m m。
