网站内链调整,wordpress flat主题,网站制作寻找客户,北京装修公司十大排名【LetMeFly】429.N 叉树的层序遍历#xff1a;广度优先搜索(BFS)
力扣题目链接#xff1a;https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
给定一个 N 叉树#xff0c;返回其节点值的层序遍历。#xff08;即从左到右#xff0c;逐层遍历#xff09;…【LetMeFly】429.N 叉树的层序遍历广度优先搜索(BFS)
力扣题目链接https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
给定一个 N 叉树返回其节点值的层序遍历。即从左到右逐层遍历。
树的序列化输入是用层序遍历每组子节点都由 null 值分隔参见示例。 示例 1 输入root [1,null,3,2,4,null,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]
输出[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]提示
树的高度不会超过 1000树的节点总数在 [0, 10^4] 之间
方法一广度优先搜索(BFS)
和之前二叉树的广度优先搜索一样我们可以使用一个队列来存放每一层的节点再让这些节点依次出队并将节点的孩子们如有入队。
时间复杂度 O ( N ) O(N) O(N)其中 N N N是节点个数空间复杂度 O ( N 2 ) O(N2) O(N2)其中 N 2 N2 N2是节点最多的一层的节点数
AC代码
C
class Solution {
public:vectorvectorint levelOrder(Node* root) {vectorvectorint ans;queueNode* q;if (root) {q.push(root);}while (q.size()) {ans.push_back({});for (int _ q.size(); _ 0; _--) {Node* thisNode q.front();q.pop();ans.back().push_back(thisNode-val);for (Node* nextNode : thisNode-children) {q.push(nextNode);}}}return ans;}
};Python
# from typing import List, Optional# Definition for a Node.
class Node:def __init__(self, valNone, childrenNone):self.val valself.children childrenclass Solution:def levelOrder(self, root: Optional[Node]) - List[List[int]]:ans []q []if root:q.append(root)while q:ans.append([])for _ in range(len(q)):thisNode q[0]q q[1:]ans[-1].append(thisNode.val)for nextNode in thisNode.children:q.append(nextNode)return ans
针对于Python的语法糖若使用两个数组可以很大程度上减少代码量甚至提高效率
# from typing import Optional, List# Definition for a Node.
class Node:def __init__(self, valNone, childrenNone):self.val valself.children childrenclass Solution:def levelOrder(self, root: Optional[Node]) - List[List[int]]:ans []a []if root:a.append(root)while a:ans.append([thisNode.val for thisNode in a])a [nextChild for thisNode in a for nextChild in thisNode.children]return ans同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/136136336
