给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
思路：参考题解：LeetCode题解
时间复杂度：O(N)，N 为树的节点数量，计算树的深度需要遍历所有节点。
空间复杂度：O(Height)，其中 Height 为二叉树的高度。由于递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，而递归的深度显然为二叉树的高度，并且每次递归调用的函数里又只用了常数个变量，所以空间复杂度为O(Height) 。
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/// 参考题解：https://leetcode.cn/problems/diameter-of-binary-tree/solutions/557966/go-yu-yan-shi-yong-quan-ju-bian-liang-la-2crn/?languageTags=golang// 【前序遍历】思想：// 任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。varresintfuncdiameterOfBinaryTree(root*TreeNode) int { res=0// 注意每次都要初始化res=0 ,不同用例在跑的时候 max会被覆盖导致 max值为上次的值dfs(root) returnres} funcdfs(node*TreeNode) int { ifnode==nil { return0 } l :=dfs(node.Left) r :=dfs(node.Right) res=max(res, l+r) // 注意：计算当前最大直径时，也可以仅计算直径边长数l+r，不需加1returnmax(l, r) +1// 加上根节点自身构成的一条直径边} funcmax(a, bint) int { ifa>b { returna } returnb} // var res int// func diameterOfBinaryTree(root *TreeNode) int {// res = 0// dfs(root)// return res - 1// }// func dfs(node *TreeNode) int {// if node == nil {// return 0// }// // 错误：最后return时已经加了1了，因此这里不用return 1// // 遍历到叶子节点，叶子节点自身不占 “边长”// // if node.Left == nil && node.Right == nil {// // return 1// // }// l := dfs(node.Left)// r := dfs(node.Right)// res = max(res, l + r + 1)// return max(l, r) + 1 // 加上根节点自身构成的一条直径边// }
