刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/diameter-of-binary-tree/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

输入：root = [1,2]
输出：1

提示：

• 树中节点数目在范围 [1, 104] 内
• -100 <= Node.val <= 100

思路

思路应该还是比较简单的，之前有过一个更加复杂一点的问题：
LeetCode-124. 二叉树中的最大路径和
不过对于此题来说，不需要考虑节点上的值，所以只需要得到：

• 能给父节点提供的最长直径(也就是最大深度)
• 以及不经过父节点、而经过自己的最长直径

再归纳一下就是：

计算每个节点作为最长直径路径上的根节点时的路径长度，比较得到最大值即可

PS. 两节点之间路径的 长度 由它们之间边数表示。边数！而非节点数！

代码

func diameterOfBinaryTree(root *TreeNode) int {
    // 兼容给出的root为nil或者没有子节点的情况
    res := 1
    var getMax func(*TreeNode) int
    getMax = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        if node.Left == nil && node.Right == nil {
            return 1
        }
        leftMax := getMax(node.Left)
        rightMax := getMax(node.Right)
        // 不经过父节点、而经过自己的最长直径
        if leftMax + rightMax + 1 > res {
            res = leftMax + rightMax + 1
        }
        // 能给父节点提供的最长`直径`(也就是最大深度)
        if leftMax > rightMax {
            return leftMax + 1
        }
        return rightMax + 1
    }
    _ = getMax(root)
    return res-1
}