<div>
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
Example 1:
<pre>Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3]. </pre>
Example 2:
<pre>Input: root = [1,2] Output: 1 </pre>
Constraints:
- The number of nodes in the tree is in the range
[1, 10<sup>4</sup>]. -100 <= Node.val <= 100
</div>
题目大意：
求树的直径：任何两个节点的最大距离
解题思路：
DFS
解题步骤：
N/A
注意事项：
- 三种情况：自己+左，自己+右，左+右，不要漏掉最后一种
- 用nonlocal就不用定义self.max_len的全局变量
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16def diameterOfBinaryTree(self, root: TreeNode) -> int:
max_len = 0
def dfs(root):
if not root:
return 0
nonlocal max_len
left = dfs(root.left) + 1
right = dfs(root.right) + 1
res = max(left, right)
total = left + right - 1
max_len = max(res, total, max_len)
return res
dfs(root)
return max_len - 1
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
