543. 二叉树的直径

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

//递归，后序遍历
var res int
func diameterOfBinaryTree(root *TreeNode) int {
    res = 0
    dfs(root)
    return res
}
func dfs(root *TreeNode) int {
    if root == nil {
        return 0
    }
    l := dfs(root.Left)
    r := dfs(root.Right)
    path := max(l, r)
    res = max(l+r, res)
    return path + 1
}
func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}