手工包网站建设策划书营销策划书

https://leetcode.cn/problems/diameter-of-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked

题目描述：给一个二叉树，返回二叉树直径最大值。直径指的是二叉树中任意一个结点到另外一个结点产生路径的长度。而长度由边来代表。

思路

1. 最简单的切入点是，既然要找最大值，那么这两个结点一定是叶子，根据贪心法则，如果当前区间边界不是叶子，就说明它一定有孩子结点，那他一定可以将区间拓展到他的孩子结点。所以最终的答案区间边界一定是叶子结点
2. 既然答案一定是叶子结点，那么孩子结点连城路径一定会经过非叶子结点，所以遍历思路就出来了。遍历非叶子结点。
3. 而答案路径很好表示，假设你选定当前这个非叶子结点作为路径通路。那么经过这个结点的最大直径，一定是左子树高度加上右子树高度。

根据上面结果整体解题思路以及大概的代码逻辑都出来了。
就是遍历一下非叶子结点，算一下左右两边子树高度，记录最大值就好了。
然后编码实际上用计算高度的递归就好了

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/func ans(root *TreeNode, res *int) int{if root == nil {return 0}left := ans(root.Left, res)right := ans(root.Right, res)tem := left + rightif tem > *res {*res = tem}if left < right {return right + 1}return left + 1
}func diameterOfBinaryTree(root *TreeNode) int {var a = 0ans(root, &a)return a
}