Leetcode 1522. N 叉树的直径

1.题目基本信息

1.1.题目描述

给定一棵 N 叉树 的根节点 root ，计算这棵树的直径长度。

N 叉树的直径指的是树中任意两个节点间路径中 最长 路径的长度。这条路径可能经过根节点，也可能不经过根节点。

（N 叉树的输入序列以层序遍历的形式给出，每组子节点用 null 分隔）

1.2.题目地址

https://leetcode.cn/problems/diameter-of-n-ary-tree/description/

2.解题方法

2.1.解题思路

深度优先搜索

时间复杂度：O(n)

2.2.解题步骤

第一步，定义维护变量。result维护最长的直径

第二步，定义递归函数。递归任务：返回从node节点开始，到达叶节点最长的两条路径的长度

2.1.递归出口；当node为叶节点时，递归退出

2.2.递归主体；使用maxLen1和maxLen2分别维护node结点到达叶节点第一长和第二长的路径长度

第三步，调用递归，更新result；并返回结果

3.解题代码

Python代码

class Solution:# 思路：深度优先搜索def diameter(self, root: 'Node') -> int:# 第一步，定义维护变量。result维护最长的直径self.result = 0# 第二步，定义递归函数。递归任务：返回从node节点开始，到达叶节点最长的两条路径的长度def dfs(node: 'Node') -> list[int]:# 2.1.递归出口if len(node.children) == 0:return [0, 0]# 2.2.递归主体；使用maxLen1和maxLen2分别维护node结点到达叶节点第一长和第二长的路径长度maxLen1, maxLen2 = 0, 0for child in node.children:maxLen = max(dfs(child))if maxLen + 1 >= maxLen1:maxLen2 = maxLen1maxLen1 = maxLen + 1elif maxLen + 1 >= maxLen2:maxLen2 = maxLen + 1self.result = max(self.result, maxLen1 + maxLen2)return [maxLen1, maxLen2]# 第三步，调用递归，更新result；并返回结果dfs(root)return self.result

4.执行结果