给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
使用深度优先搜索，计算左子树深度，右子树深度
- 结束条件：越过叶子结点。
- 递推工作：左子树的深度 left，右子树的深度 right。利用 res 记录最大的 left + right。
- 返回值：左子树和右子树深度较大的值 + 1。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.res = 0
def dfs(root):
if not root: return 0
left = dfs(root.left)
right = dfs(root.right)
self.res = max(self.res, left + right)
return max(left, right) + 1
dfs(root)
return self.res
- 时间复杂度 O(n)：其中 n 为树的结点数量。
- 空间复杂度 O(height)：其中 height 为树的高度。