遍历children_[LeetCode] 429. N叉树的层序遍历

短命女 2023-01-06 11:43 156阅读 0赞

![dc338ae9f4af9a609d6b3fd9545217f6.png][]

题目链接： https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal

难度：简单

通过率：62.6%

## 题目描述: ##

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

## 示例: ##

例如，给定一个 `3叉树` :

![b6d1814fdb4a006c3484c1d8b56c439d.png][]

返回其层序遍历:

[
    
         [1],
    
         [3,2,4],
    
         [5,6]
    
    ]

**说明:**

1.  树的深度不会超过 `1000`。
2.  树的节点总数不会超过 `5000`。

## 思路: ##

思路一：DFS

class Solution:
        def levelOrder(self, root: 'Node') -> List[List[int]]:
    
            res = []
    
            def dfs(root, depth):
                if not root: return 
                if len(res) <= depth:
                    res.append([])
                res[depth].append(root.val)
                for ch in root.children:
                    dfs(ch, depth+1)
    
            dfs(root, 0)
            return res

思路二：BFS

class Solution:
        def levelOrder(self, root: 'Node') -> List[List[int]]:
            if not root:return []
            res = []
    
            def bfs(root):
                queue = [root]
                while queue:
                    nxt = []
                    tmp = []
                    for node in queue:
                        tmp.append(node.val)
                        for ch in node.children:
                            nxt.append(ch)
                    res.append(tmp)
                    queue = nxt
    
            bfs(root)
            return res

[dc338ae9f4af9a609d6b3fd9545217f6.png]: /images/20221119/50fc9a24f43a4f8f8e7037e192b4c07e.png
[b6d1814fdb4a006c3484c1d8b56c439d.png]: https://img-blog.csdnimg.cn/img_convert/b6d1814fdb4a006c3484c1d8b56c439d.png