前往此题)

解题思路

这道题是二叉树的最大深度的变种题，它们的区别仅仅在于2和N的区别。解题办法也和二叉树的相同，深度优先和广度优先都可以解这道题。

深度优先搜索（递归法）

算法流程

过滤极端情况，root为None或者 root.children为空则返回0或1
因为我们不知道有几个分支，所以我们在遍历的时候需要将每条分支的高度放入数组中，然后取其最大值。

代码

"""
# 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
        if root.children == []: return 1

        height = [self.maxDepth(a) for a in root.children]
        return max(height) + 1

广度优先搜索（辅助栈）

借助辅助栈stack放入每层的节点，由于迭代法不像递归一样能及时返回当前层数，所以我们在栈中需要放入层数，初始值为1。
stack.append((1, root))
遍历stack, 借助变量depth来记录每条分支下的最大深度，通过max函数不断更新最大值来获得最大深度。

代码

"""
# 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:
        stack = []
        if root is not None:
            stack.append((1, root))
        depth = 0
        while stack != []:
            current_dep, root = stack.pop()
            if root is not None:
                depth = max(current_dep, depth)
                for c in root.children:
                    stack.append((current_dep+1, c))
        return depth