思路
枚举所有的最高点的最大值,然后再取max,就是全部的最大值
怎么计算一个节点作为最高点的路径最大值
其实就是以其为根节点的左子树深度加上右子树深度再加一(加上自己这个点)
递归时需要计算从当前节点往下走,深度的最大值
就是左儿子的深度最大值和右儿子的深度最大值
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans = 0
self.dfs(root)
return self.ans
def dfs(self, root):
if not root: return 0
left = self.dfs(root.left)
right = self.dfs(root.right)
self.ans = max(self.ans, left + right) # 最后是left+right
# 其实就是左右子树最大深度之和,等于路径的边数
return max(left + 1, right + 1)
# 返回当前根节点的左右子树深度最大值加一,注意叶节点的深度为0
# 样例中1-2-4路径为2,1-3路径为1,2-4-5路径为2,