添加链接描述
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def __init__(self):
self.max = 0
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.depth(root)
return self.max
def depth(self, root):
if not root:
return 0
l = self.depth(root.left)
r = self.depth(root.right)
'''每个结点都要去判断左子树+右子树的高度是否大于self.max，更新最大值'''
self.max = max(self.max, l+r)
# 返回的是高度
return max(l, r) + 1
思路：
- 典型的求树高，然后把左右子树树高相加的题目
但是需要注意一个情况：
- 最大直径可能并不是左右子树相加，也可能是一颗子树中的最大直径
- 所以需要引入一个全局变量，记录每一个节点的最大直径
- 添加
__init__(self)函数，然后把max值作为全局变量 - 每次比较
self.max = max(self.max, l+r)这样才能不遗漏最大值
