二叉树的直径（Diameter of Binary Tree）

题目描述
给定一棵二叉树，其直径（Diameter）定义为树中任意两节点之间最长路径的“边数”。这条路径不一定穿过根节点。我们需要设计算法计算二叉树的直径。

举个例子：

          1
         / \
        2   3
       / \     
      4   5    

这棵树的直径是3，对应路径[4,2,1,3]或[5,2,1,3]，都经过3条边。注意路径可以是任意两节点间的路径，未必过根。

解题过程

步骤1：理解直径的含义
树中任意两点间只有一条简单路径，路径长度以边数度量。直径就是这些长度中的最大值。
关键观察：对于任一节点，经过它的最长路径长度 = 其左子树深度 + 右子树深度（这里深度定义为从该节点到其子树中最深节点的边数）。
那么，整个树的直径 = 对所有节点的 “左子树深度 + 右子树深度” 取最大值。

步骤2：定义深度
在二叉树中，节点 root 的深度（或称高度）通常定义为：

• 空节点深度 = 0
• 非空节点深度 = 1 + max(左子树深度, 右子树深度)
  注意：这个“深度”是从该节点向下到叶子的最大边数。例如，叶节点的深度 = 0（因为向下无边）。

步骤3：递归计算与直径更新
我们可以在递归计算每个节点深度的同时，计算经过该节点的路径长度（左深度 + 右深度），并用一个变量记录全局最大值。
具体过程：

• 深度计算函数 depth(node)：
  • 如果 node 为空，返回 0。
  • 否则，递归计算 left_depth = depth(node.left)，right_depth = depth(node.right)。
  • 当前节点的“直径候选值”是 left_depth + right_depth。用其更新全局最大直径。
  • 该节点返回的深度是 1 + max(left_depth, right_depth)。

步骤4：算法步骤

1. 初始化 max_diameter = 0。
2. 定义递归函数 dfs(root)：
   a. 若 root 为空，返回 0。
   b. 递归计算左子树深度 L = dfs(root.left)。
   c. 递归计算右子树深度 R = dfs(root.right)。
   d. 更新 max_diameter = max(max_diameter, L + R)。
   e. 返回 1 + max(L, R)。
3. 从根节点调用 dfs(root)。
4. 返回 max_diameter。

步骤5：示例演示
以上述树为例：

        1
       / \
      2   3
     / \     
    4   5    

计算过程：

• 节点4：L=0, R=0 → 更新直径=0，返回深度1。
• 节点5：L=0, R=0 → 更新直径=0，返回深度1。
• 节点2：L=1（节点4的深度）, R=1（节点5的深度） → 更新直径=1+1=2，返回深度=1+max(1,1)=2。
• 节点3：L=0, R=0 → 更新直径不变，返回深度1。
• 节点1：L=2（节点2的深度）, R=1（节点3的深度） → 更新直径=max(2, 2+1=3)=3，返回深度=1+max(2,1)=3。
  最终直径=3。

步骤6：复杂度分析

• 时间复杂度 O(N)：每个节点访问一次。
• 空间复杂度 O(H)：递归栈深度，H为树高，最坏O(N)（斜树），平均O(log N)。

关键点

• 直径是边的数量，不是节点数。
• 路径不一定过根，所以需要遍历每个节点并计算“左右深度和”。
• 深度递归返回时，返回的是该节点向下的最大深度，用于父节点计算。