### 题目描述 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。 ### 输入输出 #### 示例1 ``` 输入：root = [1,null,3,2,4,null,5,6] 输出：[[1],[3,2,4],[5,6]] ``` #### 示例2 ``` 输入：root = [1,null,3,2,4,null,5,6] 输出：[[1],[3,2,4],[5,6]] ``` **提示** - 树的高度不会超过 1000 - 树的节点总数在 [0, 10^4] 之间 ### 题目解答 #### 思路 层序遍历采用队列的方式实现，在开始的时候记录该层有多少个节点，对于这一层只访问这么多，之后入队的是下一层不再进行访问。 **算法复杂度** 时间复杂度：n个节点每个节点访问一次复杂度$$O(n)$$ 空间复杂度：队列中最多有n-1个节点入队，空间复杂度$$O(n)$$ #### 代码实现 ```python class Solution: def levelOrder(self, root: 'Node') -> List[List[int]]: res = list() if root is None: return res queue = [root] while len(queue) > 0: size = len(queue) layer = list() while size > 0: node = queue[0] del queue[0] layer.append(node.val) if node.children is not None: queue.extend(node.children) size -= 1 res.append(layer) return res ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复