LeetCode | 0429. N 叉树的层序遍历【Python】

逃离我推掉我的手 2023-01-05 05:30 236阅读 0赞

## Problem ##

[LeetCode][]

Given an n-ary tree, return the *level order* traversal of its nodes’ values.

*Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).*

**Example 1:**

![img][]

Input: root = [1,null,3,2,4,null,5,6]
    Output: [[1],[3,2,4],[5,6]]

**Example 2:**

![img][img 1]

Input: 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]
    Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

**Constraints:**

*  The height of the n-ary tree is less than or equal to `1000`
 *  The total number of nodes is between `[0, 104]`

## 问题 ##

[力扣][Link 1]

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

**示例 1：**

![img][]

输入：root = [1,null,3,2,4,null,5,6]
    输出：[[1],[3,2,4],[5,6]]

**示例 2：**

![img][img 1]

输入：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**

二叉树层次遍历用 BFS 的时候每次都是把左右子树加入队列，N叉树每次都是把所有子树加入队列。

### Python3 代码 ###

""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """
    
    class Solution:
        def levelOrder(self, root: 'Node') -> List[List[int]]:
            import collections
            res = []
            if not root:
                return res
            
            q = collections.deque()
            q.append(root)
            # BFS
            while q:
                tmp = []
                for _ in range(len(q)):
                    node = q.popleft()
                    tmp.append(node.val)
                    # 使用extend在列表末尾一次追加多个值
                    q.extend(node.children)
                res.append(tmp)
            return res

## GitHub 链接 ##

[Python][]

[LeetCode]: https://leetcode.com/problems/n-ary-tree-level-order-traversal/
[img]: /images/20221119/d9747a21ec404ea6a9cdd8d0bc9b213c.png
[img 1]: /images/20221119/a20ce6f760634b7ca56877ffa5b7b26a.png
[Link 1]: https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
[Python]: https://github.com/Wonz5130/LeetCode-Solutions/blob/master/solutions/0429-N-ary-Tree-Level-Order-Traversal/0429.py