难度: Easy
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2] 输出：1
提示：
[1, 104] 内-100 <= Node.val <= 100运行时间: 52 ms
内存: 16.8 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
m = 0
def dfs(root):
nonlocal m
if root is None:
return 0
l = dfs(root.left)
r = dfs(root.right)
m = max(m, l+r)
return max(l, r) + 1
dfs(root)
return m
这个题解采用了DFS的思路。首先定义一个全局变量m来记录最大直径长度。然后对二叉树进行后序遍历，在遍历过程中，对每个节点，计算以该节点为根的左右子树的最大深度l和r，然后用l+r更新最大直径m。遍历结束后，m即为整棵树的最大直径。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
m = 0
def dfs(root):
nonlocal m
if root is None:
return 0
# 递归计算左子树的最大深度
l = dfs(root.left)
# 递归计算右子树的最大深度
r = dfs(root.right)
# 用左右子树最大深度之和更新直径最大值
m = max(m, l+r)
# 返回以当前节点为根的子树的最大深度
return max(l, r) + 1
dfs(root)
return m
在计算二叉树的直径时，需要知道每个节点的左右子树的最大深度，这是因为每个节点的最大直径可以看作是它左子树的最大深度加上它右子树的最大深度。后序遍历先访问一个节点的所有子节点后才访问该节点本身，这使得在访问任何一个节点之前，它的左右子树的深度已经被计算出来了，从而可以直接用来更新直径。如果使用前序或中序遍历，我们需要额外的机制来存储和更新每个节点的子树深度信息，这会使算法更加复杂。
是的，这种方法能准确覆盖所有节点对的最长路径。二叉树的直径定义为树中任意两个节点间的最长路径的长度，而这条路径可以通过树中的某个节点（称为路径的根节点）连接其左右子树中的最长路径来构成。因此，对于每个节点，计算其左子树的最大深度和右子树的最大深度之和，就能得到经过该节点的最长路径的长度。通过遍历所有节点并更新这个值，我们可以确保找到整棵树的直径。
全局变量m在递归过程中用于存储当前遍历到的所有节点的最大直径。在递归函数中，每当计算出一个节点的左子树最大深度和右子树最大深度后，就将这两个值相加得到的和与当前的m进行比较，并取两者之间的较大值更新m。这样，随着递归过程的推进，每个节点都尝试更新m，确保m始终保持为遇到的最大直径。由于m被声明为nonlocal，它可以在递归函数内被修改，而修改会影响到函数外部的值。
在递归函数`dfs`中，`l`和`r`分别是当前节点左右子树的最大深度。计算当前节点的最大深度时，应该选择左子树和右子树中深度较大的一个，然后加上当前节点本身，即`max(l, r) + 1`。这样确保了返回的值代表从当前节点到其最深叶子节点的最长路径长度。这个值用于上一层递归中父节点的最大深度计算，确保每个节点都能正确计算其子树的最大深度。