难度: Medium
Submission
运行时间: 38 ms
内存: 0.0 MB
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
"""
class Solution:
def diameter(self, root: 'Node') -> int:
"""
:type root: 'Node'
:rtype: int
"""
ans = 0
def heights(node):
nonlocal ans
if not node: return 0
if not node.children: return 1
toph1, toph2 = 0, 0
for nei in node.children:
h = heights(nei)
if h > toph1:
toph1, toph2 = h, toph1
elif h > toph2:
toph2 = h
ans = max(ans, toph1 + toph2)
return max(toph1, toph2) + 1
heights(root)
return ans
Explain
该题解通过递归的方式计算N叉树的直径。递归函数`heights`计算并返回从当前节点到其最远叶子节点的最大高度。同时，该函数维护一个全局变量`ans`用来记录遍历过程中遇到的最大直径。对于每个节点，我们考虑通过该节点的两条最长路径（可能的直径），这是通过维护两个最大高度`toph1`和`toph2`实现的。每次访问子节点时，更新这两个最大高度，如果当前节点的高度大于`toph1`，则更新`toph1`和`toph2`；如果只大于`toph2`，则只更新`toph2`。最后，`toph1`和`toph2`的和可能会更新全局最大直径`ans`。
时间复杂度: O(N)
空间复杂度: O(N)
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
"""
class Solution:
def diameter(self, root: 'Node') -> int:
"""
:type root: 'Node'
:rtype: int
"""
ans = 0 # 最大直径的长度
def heights(node):
nonlocal ans # 引用外部的最大直径变量
if not node: return 0 # 空节点的高度为0
if not node.children: return 1 # 没有子节点，高度为1
toph1, toph2 = 0, 0 # 初始化两个最高的子节点高度
for nei in node.children:
h = heights(nei) # 递归计算子节点的高度
if h > toph1:
toph1, toph2 = h, toph1 # 更新最高和次高
elif h > toph2:
toph2 = h # 更新次高
ans = max(ans, toph1 + toph2) # 可能的最大直径
return max(toph1, toph2) + 1 # 返回节点的最大高度
heights(root) # 从根节点开始计算高度
return ans # 返回计算的最大直径
Explore
在N叉树中，节点的直径可能是通过该节点连接其两个最长子树的路径的长度。因此，为了计算通过当前节点的可能直径，我们需要知道从该节点出发的两个最长路径（子树高度）。`toph1`和`toph2`分别维护这两个最大高度，使我们能够在每个节点处计算通过该节点的最长路径，即可能的直径。
在递归过程中，对每个子节点计算其高度后，我们会比较这个高度与当前的`toph1`和`toph2`。如果当前子节点的高度超过`toph1`，则说明我们找到了一个新的最长路径，将`toph1`更新为这个新的最长路径，原`toph1`变为`toph2`。如果子节点的高度没有超过`toph1`但超过了`toph2`，则只更新`toph2`。这样保证了`toph1`和`toph2`始终是当前节点两个最长子路径的高度。
在每个节点，通过该节点的直径可以视为其两个最长子树的高度之和。因此，在更新`toph1`和`toph2`后，我们通过计算`toph1 + toph2`来获取通过当前节点的最大直径，并与全局变量`ans`进行比较。如果`toph1 + toph2`的值大于现有的`ans`，则更新`ans`。这种方法确保了无论直径穿过树的哪个部分，都能够捕获并更新最大直径。
是的，返回值`max(toph1, toph2) + 1`确实表示我们选择经过较高子树的路径作为当前节点的高度。这是因为树中每个节点的高度定义为从该节点到其最远叶子节点的路径长度。因此，从当前节点出发的最高路径决定了该节点的高度。`max(toph1, toph2)`选出两个最长子路径中的较长者，`+1`表示加上当前节点到该子节点的一步距离。