二叉树的直径问题

题目描述
给定一棵二叉树，你需要计算它的直径长度。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能不经过根节点，但必须保证是连通两个叶节点的简单路径（即不会重复经过同一个节点）。路径长度由节点之间的边数表示。

关键点分析

1. 直径可能经过根节点，也可能完全位于某棵子树中。
2. 直径的长度可分解为：左子树的最大深度 + 右子树的最大深度（若路径经过当前节点）。
3. 需要遍历所有节点，计算以每个节点为根的子树直径，并记录最大值。

解题思路

1. 问题转化

   • 对于任意节点，若其左子树深度为 L，右子树深度为 R，则经过该节点的直径长度为 L + R。
   • 全局直径是所有节点中 L + R 的最大值。

2. 深度计算与直径更新

   • 采用后序遍历（左右根），在计算节点深度的同时更新直径。
   • 节点深度定义为从该节点到最远叶节点的边数（叶节点深度为0）。

3. 算法步骤

   • 初始化全局变量 maxDiameter 记录当前最大直径。
   • 递归函数 depth(node) 返回以 node 为根的子树深度：
     • 若节点为空，返回深度 -1（空节点无边，深度为-1便于边数计算）。
     • 递归计算左子树深度 leftDepth。
     • 递归计算右子树深度 rightDepth。
     • 更新 maxDiameter = max(maxDiameter, leftDepth + rightDepth + 2)（+2表示连接左右子树的边）。
     • 返回当前子树深度 max(leftDepth, rightDepth) + 1。

逐步示例
以二叉树为例：

      1
     / \
    2   3
   / \     
  4   5    

1. 节点4：深度0，左右子树深度-1，直径=0。
2. 节点5：深度0，直径=0。
3. 节点2：左子树深度0（节点4），右子树深度0（节点5），直径=0+0+2=2。
4. 节点3：深度0，直径=0。
5. 节点1：左子树深度1（节点2的深度），右子树深度0（节点3），直径=1+0+2=3。
   最终直径为3（路径4→2→1→3或5→2→1→3，边数为3）。

代码实现（Python）

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.maxDiameter = 0
        
        def depth(node):
            if not node:
                return -1  # 空节点深度为-1，使叶节点深度为0
            leftDepth = depth(node.left)
            rightDepth = depth(node.right)
            # 更新直径：左深度+右深度+2条连接左右子树的边
            self.maxDiameter = max(self.maxDiameter, leftDepth + rightDepth + 2)
            return max(leftDepth, rightDepth) + 1  # 返回当前子树深度
        
        depth(root)
        return self.maxDiameter

复杂度分析

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

总结

• 核心思路：将直径问题转化为对每个节点计算“左右子树深度和”的最大值。
• 关键技巧：后序遍历同时完成深度计算与直径更新，避免重复计算。
• 边界处理：空节点深度设为-1可统一边数计算逻辑。