我来给你讲解 LeetCode 第 543 题「二叉树的直径」。

题目描述

给定一棵二叉树，你需要计算它的直径长度。二叉树的直径是树中任意两个结点之间路径长度的最大值。这条路径可能穿过也可能不穿过根结点。

注意：两结点之间的路径长度是以它们之间边的数目表示。

解题思路

第一步：理解直径的定义

二叉树的直径实际上是：对于树中的每个节点，计算「左子树高度 + 右子树高度」的最大值。

为什么？因为任意两个节点之间的最长路径，必然经过某个节点作为最高点，路径长度就是这个节点的左子树深度加上右子树深度。

第二步：基础思路分析

1. 对于每个节点，我们需要知道它的左子树深度和右子树深度
2. 直径 = max(当前节点的左深度 + 右深度, 已经计算过的直径)
3. 节点的深度 = max(左深度, 右深度) + 1

第三步：递归函数设计

我们设计一个递归函数 depth(node)：

• 返回值：以该节点为根的子树的最大深度
• 在递归过程中，同时更新全局的直径最大值

第四步：详细步骤分解

步骤 1：特殊情况处理

• 如果树为空，直径为 0

步骤 2：递归函数逻辑

def depth(node):
    if node is None:
        return 0
    
    left_depth = depth(node.left)      # 左子树深度
    right_depth = depth(node.right)    # 右子树深度
    
    # 更新直径：当前节点的路径长度 = left_depth + right_depth
    diameter = max(diameter, left_depth + right_depth)
    
    # 返回当前节点的深度
    return max(left_depth, right_depth) + 1

步骤 3：执行过程

1. 从根节点开始递归
2. 对于每个节点，先递归计算左右子树的深度
3. 用左右深度之和更新直径
4. 返回当前节点的深度给父节点

第五步：具体例子演示

考虑二叉树：

      1
     / \
    2   3
   / \     
  4   5    

计算过程：

• 节点4：深度=1，直径=0（无子节点）
• 节点5：深度=1，直径=0
• 节点2：左深度=1，右深度=1，路径长度=2，深度=2
• 节点3：深度=1，直径=0
• 节点1：左深度=2，右深度=1，路径长度=3，深度=3

最终直径 = max(2, 3) = 3（路径 4→2→1→3 或 5→2→1→3）

第六步：完整代码实现

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.diameter = 0
        
        def depth(node):
            if not node:
                return 0
                
            left_depth = depth(node.left)
            right_depth = depth(node.right)
            
            # 更新直径
            self.diameter = max(self.diameter, left_depth + right_depth)
            
            # 返回当前节点的深度
            return max(left_depth, right_depth) + 1
        
        depth(root)
        return self.diameter

第七步：复杂度分析

• 时间复杂度：O(n)，每个节点只访问一次
• 空间复杂度：O(h)，h为树的高度，主要是递归栈空间

第八步：关键点总结

1. 直径是路径上边的数量，不是节点数量
2. 直径不一定经过根节点，可能完全在某个子树中
3. 采用后序遍历（左右根）可以自然获得子树信息
4. 在递归计算深度的同时更新直径最大值

这个解法巧妙地将深度计算和直径更新结合在一起，通过一次遍历即可解决问题。