【Leetcode】559—Maximum Depth of N

一、题目描述

给定一个 N 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

二、代码实现

方法一：BFS

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        if root == None: return 0
        queue = [root]
        layer_index = 0
        max_layer_index = 0
        while queue:
            layer = []
            layer_index = layer_index + 1
            for idx in range(len(queue)):
                ele = queue.pop(0)
                if not ele.children: 
                    if layer_index > max_layer_index:
                        max_layer_index = layer_index
                    continue
                for child in ele.children:
                    queue.append(child)
        return max_layer_index 

方法二：DFS

求一个树的高度，完全可以转成一个递归问题，树最大高度 = 1 + 子树最大高度

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        if not root: return 0
        if not root.children: return 1
        depth = 1 + max(self.maxDepth(child) for child in root.children)
        return depth