写点什么

[Day31]-[二叉树] 二叉树的直径

作者:方勇(gopher)
  • 2022 年 4 月 30 日
  • 本文字数:623 字

    阅读完需:约 2 分钟

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


示例 :给定二叉树


      1     / \    2   3   / \       4   5    
复制代码


返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

func TestDiameterOfBinaryTree(t *testing.T) {	root := &TreeNode{ // 初始化一棵树		Val: 1,		Left: &TreeNode{			Val: 2,			Left: &TreeNode{				Val: 4,				Left: &TreeNode{					Val: 6,				},			},			Right: &TreeNode{				Val: 5,				Left: &TreeNode{					Val: 7,				},			},		},		Right: &TreeNode{			Val: 3,		},	}	var ans int                           // 最大直径 默认是0	var solution func(root *TreeNode) int // 解决方案呢	var max func(x, y int) int            // 取最大值	var dfs func(root *TreeNode) int      // 深度遍历	max = func(x, y int) int {		if x > y {			return x		}		return y	}	dfs = func(root *TreeNode) int {		if root == nil { // 递归终止条件			return 0		}		l := dfs(root.Left)   // 左侧高度		r := dfs(root.Right)  // 右侧高度		dept := max(l, r) + 1 // 数的最大高度		ans = max(ans, l+r)   // 数的最大直径 = 左侧最大高度 + 右侧的最大高度
return dept } solution = func(root *TreeNode) int { dfs(root) return ans } t.Log(solution(root))}
复制代码


用户头像

Dead or Alive. 生存战斗是知识的源泉! 2018.11.08 加入

我是一名SRE哨兵,目前是好大夫基础架构部高级工程师。专注于 SRE,微服务、中间件的稳定性和可用性建设,整体负责好大夫服务治理云平台的设计和搭建!

评论

发布
暂无评论
[Day31]-[二叉树]二叉树的直径_LeetCode_方勇(gopher)_InfoQ写作社区