LeetCode-543.二叉树的直径 - sheep44044的小站

二叉树#

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

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

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

示例 1：

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

示例 2：

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

递归的解法

思路：可以认为是所有节点中左右子树的深度和的最大值 or 不经过根节点的最大值

所以在求maxDepth时，维护一个全局的最大值maxDiameter即可，存储到达跟节点前的最大值

1
/**
2
 * Definition for a binary tree node.
3
 * type TreeNode struct {
4
 *     Val int
5
 *     Left *TreeNode
6
 *     Right *TreeNode
7
 * }
8
 */
9
func diameterOfBinaryTree(root *TreeNode) int {
10
    if root == nil {
11
        return 0
12
    }
13
    maxDiameter := 0
14

15
    var maxDepth func(*TreeNode) int
16
    maxDepth = func(root *TreeNode) int {
17
        if root == nil {
18
            return 0
19
        }
20

21
        leftHeight := maxDepth(root.Left)
22
        rightHeight := maxDepth(root.Right)
23

24
        if leftHeight + rightHeight > maxDiameter {
25
            maxDiameter = leftHeight + rightHeight
26
        }
27

28
        return max(leftHeight, rightHeight) + 1
29
    }
30
    maxDepth(root)
31

32
    return maxDiameter
33
}