❌ LeetCode 543 - 二叉树的直径

问题描述

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root。

两节点之间路径的长度由它们之间边数表示。

示例 1：

输入： root = [1,2,3,4,5]
输出： 3
解释： 直径为 3，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

1
2
3

  1
 /
2

输入： root = [1,2]
输出： 1

提示：

树中节点数目在范围 [1, 10^4] 内
-100 <= Node.val <= 100

错误解法与分析

我最初对这个问题的理解是计算树的高度，而没有考虑到直径的特殊性质。我的初始思路是通过计算树的最大深度来解决问题：

// ❌ 错误思路：仅计算树的高度
func diameterOfBinaryTree(root *TreeNode) int {
    if root == nil {
        return 0
    }
  
    leftHeight := maxDepth(root.Left)
    rightHeight := maxDepth(root.Right)
  
    return leftHeight + rightHeight // 错误：没有与当前已知最大直径做比较
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
  
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

这个解法在以下情况下失败：

错误原因分析

我的错误在于：

没有理解直径的完整定义：直径是树中任意两个节点之间的最长路径，这不一定穿过根节点。
只计算了根节点的最大深度：我只计算了从根节点出发的左右子树深度和，但没有考虑到直径可能完全存在于左子树或右子树中。
缺乏全局视角：没有在递归过程中维护全局的最大直径值，导致无法比较不同子树中可能的直径。

最关键的错误是没有认识到：每个节点都可能是直径路径的"拐点"，需要比较所有可能的路径长度来找到最大直径。

正确解法

经过分析，改进的解法是使用深度优先搜索（DFS），在递归计算每个节点的高度的同时，更新全局最大直径值：

func diameterOfBinaryTree(root *TreeNode) int {
    res := 0
    dfsDiameterOfBinaryTree(root, &res)
    return res
}

func dfsDiameterOfBinaryTree(node *TreeNode, res *int) int {
    if node == nil {
        return 0
    }
  
    // 递归计算左右子树的深度
    leftDepth := dfsDiameterOfBinaryTree(node.Left, res)
    rightDepth := dfsDiameterOfBinaryTree(node.Right, res)
  
    // 更新全局最大直径（左子树深度 + 右子树深度）
    *res = max(*res, leftDepth + rightDepth)
  
    // 返回当前节点为根的子树的最大深度
    return max(leftDepth, rightDepth) + 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

为什么这个解法可以工作

使用DFS计算深度：通过深度优先搜索，我们可以计算每个节点的左右子树深度。
全局变量记录最大直径：使用指针 res 在递归过程中持续更新最大直径值。
比较每个可能的"拐点"：对于每个节点，我们计算:
- 当前节点作为"拐点"的路径长度 = 左子树深度 + 右子树深度
- 将这个值与已知的最大直径比较并更新

这种方法能够考虑到所有可能的路径，包括不经过根节点的路径，从而找到真正的最大直径。

算法可视化

考虑下面的二叉树：

执行过程如下：

从根节点 1 开始DFS
计算节点 2 的深度:
- 节点 4 深度 = 1
- 节点 5 深度 = 1
- 节点 2 的左右子树最大深度和 = 1 + 1 = 2
- 更新最大直径 res = 2
计算节点 3 的深度:
- 节点 3 没有子节点，深度 = 1
根节点 1 的左右子树最大深度和 = 2 + 1 = 3
- 更新最大直径 res = 3

最终返回最大直径 3，对应路径 [4,2,1,3] 或 [5,2,1,3]。

复杂度分析

时间复杂度：O(n)，其中 n 是树中的节点数。每个节点只被访问一次。
空间复杂度：O(h)，其中 h 是树的高度。在最坏情况下（树呈线性），空间复杂度为 O(n)。

学习总结

通过这道题，我学到了以下几点：

树的直径特性：树的直径不一定经过根节点，可能存在于任意子树中。
DFS的巧妙应用：在计算节点高度的同时，可以顺便解决其它问题。
全局变量在递归中的使用：通过传递指针，在递归过程中维护全局状态。
问题转化思想：将直径问题转化为"以每个节点为拐点的最长路径"问题。

这个问题提醒我，在解决树相关问题时，要注意考虑可能的路径是否需要经过根节点，以及如何在递归过程中高效地收集和更新全局信息。