559. N 叉树的最大深度

Difficulty
easy
Tags
二叉树
URL
https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/
Star
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
示例 1：
notion imagenotion image
输入：root = [1,null,3,2,4,null,5,6]
输出：3
示例 2：
notion imagenotion image
输入：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] 之间。

法1 递归法

思路
和
🏒
104. 二叉树的最大深度 类似，只不过现在每个节点不止由两个子树
self.childern 是个列表，存放子树根节点的应用，无子节点时，列表长度为0
题解
"""
# 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 root is None:
            return 0
        # 该节点为叶子节点
        if len(root.children) == 0:
            return 1
        # 将每一棵子树的高度存到temp_list中
        temp_list = []
        for temp_tree in root.children:
            temp_list.append(self.maxDepth(temp_tree)) 
        depth = max(temp_list) + 1
        return depth
优化，上述代码在遍历子节点前，先判断了是否有子节点。其实可以不用判断，在temp_list 先添加0
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if root is None:
            return 0
        childDepth = [0]
        for node in root.children:
            childDepth.append(self.maxDepth(node))
        return max(childDepth) + 1
还有如下的一种方法
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if root is None:
            return 0
        childDepth = []
        for childNode in root.children:
            childDepth.append(self.maxDepth(childNode))
        return max(childDepth,default=0) + 1

法2 层次遍历

思路
和
🏒
104. 二叉树的最大深度 类似。只不过是在添加某个节点的子节点时，要判断该节点的children属性再取逐个添加
题解
"""
# 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:
        result = 0
        if root is None:
            return result
        queue = []
        queue.append(root)
        while len(queue) > 0:
            temp_len = len(queue)
            while temp_len > 0:
                temp_node = queue.pop(0)
                temp_len -= 1
                # 将该节点的子节点存放到队列中
                if len(temp_node.children) > 0:
                    for temp_tree in temp_node.children:
                        queue.append(temp_tree)
            # 遍历完一层后，result+1
            result += 1
        return result