LeetCode | 0559. N 叉树的最大深度【Python】

末蓝、 2023-01-10 10:22 114阅读 0赞

## Problem ##

[LeetCode][]

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

*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: 3

**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: 5

**Constraints:**

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

## 问题 ##

[力扣][Link 1]

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

**示例 1：**

![img][]

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

**示例 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]
    输出：5

**提示：**

*  树的深度不会超过 1000 。
 *  树的节点数目位于 \[0, 10^4\] 之间。

## 思路 ##

**DFS**

### Python3 代码 ###

**BFS**

### Python3 代码 ###

""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """
    
    class Solution:
        def maxDepth(self, root: 'Node') -> int:
            # BFS
            import collections
            # 特判，不写会报错
            if not root:
                return 0
            
            q = collections.deque()
            q.append(root)
            depth = 0
            while q:
                for _ in range(len(q)):
                    node = q.popleft()
                    for child in node.children:
                        q.append(child)
                depth += 1
            return depth

## GitHub 链接 ##

[Python][]

[LeetCode]: https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
[img]: /images/20221119/7ff451f1a260435a88405d2b0d90e726.png
[img 1]: https://img-blog.csdnimg.cn/img_convert/481a463e68315c2a1a14ec0d9522c4dd.png
[Link 1]: https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/
[Python]: https://github.com/Wonz5130/LeetCode-Solutions/blob/master/solutions/0559-Maximum-Depth-of-N-ary-Tree/0559.py