难度: Easy
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：3
示例 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] 输出：5
提示：
1000 。[0, 104] 之间。运行时间: 23 ms
内存: 17.4 MB
"""
# 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:
if not root:
return 0
queue = collections.deque([root])
deepth = 0
while queue:
deepth += 1
for _ in range(len(queue)):
node = queue.popleft()
for child in node.children:
queue.append(child)
return deepth
该题解使用了广度优先搜索（BFS）的思路来解决 N 叉树的最大深度问题。具体步骤如下： 1. 如果根节点为空，直接返回深度 0。 2. 将根节点加入队列，初始化深度为 0。 3. 当队列不为空时，进行以下操作： - 将当前深度加 1。 - 遍历当前队列中的所有节点： - 从队列中取出一个节点。 - 将该节点的所有子节点加入队列。 4. 重复步骤 3，直到队列为空。 5. 返回最终的深度值。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def maxDepth(self, root: 'Node') -> int:
if not root:
return 0
# 初始化队列，并将根节点加入队列
queue = collections.deque([root])
deepth = 0
# BFS 遍历
while queue:
# 当前深度加 1
deepth += 1
# 遍历当前队列中的所有节点
for _ in range(len(queue)):
# 取出队首节点
node = queue.popleft()
# 将该节点的所有子节点加入队列
for child in node.children:
queue.append(child)
# 返回最终的深度值
return deepth
广度优先搜索（BFS）的核心目的是逐层探索图或树的结构，确保每一层的节点都被完全访问后，才移至下一层。队列（Queue）是一种先进先出（FIFO）的数据结构，这使得在处理时最先被加入队列的节点（即当前层的节点）最先被处理和移出，然后其子节点（即下一层的节点）随后被加入队列。这种处理顺序正好符合BFS逐层访问的需求。相反，如果使用栈（一种后进先出的数据结构），则会变为深度优先搜索（DFS），因为你会持续向下探索到叶子节点，而非按层次展开。
在算法中，每次从队列中取出节点时，都会遍历该节点的所有子节点。具体来说，对于每个被取出的节点，我们使用一个循环来遍历此节点的 `children` 属性，该属性包含了所有直接子节点的列表。遍历过程中，每个子节点都会被依次加入到队列的尾部。这样可以确保所有子节点都会被考虑到，并且按照它们在树结构中的自然顺序加入到队列中，保持了广度优先搜索的顺序性和完整性。
在处理非常不平衡的N叉树，比如链状结构（每个节点仅有一个子节点）时，该BFS算法的性能会受到一定影响，但主要是在空间复杂度上。对于链状的N叉树，树的深度与节点总数相等，即深度最大。在BFS中，虽然每次只处理一个节点，整个过程的时间复杂度仍为O(n)，其中n是节点数，因为每个节点都需要被访问一次。但由于每个节点依次进入队列，队列在整个过程中始终保持节点，因此空间复杂度也是O(n)。总体而言，BFS在处理极端不平衡的树时在时间和空间复杂度上与处理平衡树相比差异不大，主要区别在于实际运行时内存的使用情况可能更高。