树的直径
一句话说明
树的直径就是任意两点间最长路径，等价于“某个节点左深度 + 右深度”的最大值。
Go 代码
func diameterOfBinaryTree(root *TreeNode) int {
ans := 0
var depth func(node *TreeNode) int
depth = func(node *TreeNode) int {
if node == nil {
return 0
}
left := depth(node.Left)
right := depth(node.Right)
if left+right > ans {
ans = left + right
}
if left > right {
return left + 1
}
return right + 1
}
depth(root)
return ans
}关键点
直径和高度很像，但直径更新的是“拐弯后的整条路径”，高度只会向父节点返回一条链。