golang二叉树的最长直径
时间: 2023-07-26 22:07:35 浏览: 92
二叉树的直径定义为树中任意两个节点路径长度的最大值。其实我们可以将二叉树的直径问题转化为树的最大深度问题,具体做法是:对于每个节点,计算它左右子树的深度之和,取其中的最大值,就是该节点为根节点的子树的直径;然后再对所有子树的直径取最大值,就是整棵二叉树的直径。
下面是使用 Golang 实现二叉树的最长直径的代码:
```go
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}
func diameterOfBinaryTree(root *TreeNode) int {
if root == nil {
return 0
}
leftDepth := maxDepth(root.Left)
rightDepth := maxDepth(root.Right)
maxDiameter := leftDepth + rightDepth
return max(maxDiameter, max(diameterOfBinaryTree(root.Left), diameterOfBinaryTree(root.Right)))
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
```
其中 `maxDepth` 函数计算给定节点的最大深度,`diameterOfBinaryTree` 函数递归计算每个节点为根节点的子树的直径,最后返回整棵二叉树的直径。`max` 函数返回两个数中的最大值。