跳转至

LC543 - 二叉树的直径

Diameter.go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package BinaryTree

type diameterRet struct {
    height, diameter int
}

func diameterOfBinaryTree(root *TreeNode) int {
    return diameterFunc(root).diameter
}

func diameterFunc(root *TreeNode) diameterRet {
    if root == nil {
        return diameterRet{
            height:   0,
            diameter: 0,
        }
    }
    leftRet := diameterFunc(root.Left)
    rightRet := diameterFunc(root.Right)
    return diameterRet{
        height:   max(leftRet.height, rightRet.height) + 1,
        diameter: max(leftRet.diameter, rightRet.diameter, leftRet.height+rightRet.height),
    }
}

树型DP