LeetCode二叉树直径题解代码 4个测试用例失败原因排查

在解答LeetCode平台算法题《Diameter of a Binary Tree（二叉树的直径）》时，编写的求解代码可正确通过100/104个测试用例，始终无法定位剩余4个测试用例运行失败的原因与代码逻辑缺陷。本次随问题附上题目原文截图、报错用例相关截图，具体实现代码如下：

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        left_root = root.left   # 根节点的左子节点
        right_root = root.right # 根节点的右子节点
        
        def dfs(root: Optional[TreeNode]) -> int: # 计算节点高度
            if not root:
                return 0
            
            left = dfs(root.left)
            right = dfs(root.right)
            
            return 1 + max(left, right)
        
        left_depth = dfs(left_root) # 计算根节点左右子树深度
        right_depth = dfs(right_root)
        
        return left_depth + right_depth # 返回两侧深度和

代码核心缺陷 #

代码逻辑存在根本性认知错误：默认二叉树的最长直径一定经过整棵树的根节点。
二叉树直径的定义是树中任意两节点之间最长路径的边数，这条路径完全可能不经过整棵树的根节点，只存在于左子树或者右子树内部。现有代码只计算了根节点左右子树的高度之和，完全没有考虑子树内部存在更长路径的情况，这就是剩余4个测试用例无法通过的根本原因。

举个最简单的反例：
如果树结构是根节点只有左子节点，这个左子节点又分别挂了深度为3的左子树和深度为3的右子树，此时整棵树的直径是6，路径完全在左子树内部，不经过整棵树的根。按照现有代码逻辑，计算出来的结果是根节点左子树高度（4）+右子树高度（0）=4，和正确值存在偏差，自然会报错。

修正方案 #

在深度优先搜索计算节点高度的过程中，同步维护一个全局最大直径值：

• 每遍历到一个节点，先递归计算它左右子树的高度
• 把当前节点的左右子树高度相加，这个值就是以当前节点为最高点的路径长度，和全局最大值比较并更新
• 递归返回当前节点的高度（1+左右子树高度的最大值），供上层节点计算使用

修正后的可通过代码参考：

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        max_dia = 0
        def dfs(node):
            nonlocal max_dia
            if not node:
                return 0
            left_h = dfs(node.left)
            right_h = dfs(node.right)
            # 更新全局最大直径
            max_dia = max(max_dia, left_h + right_h)
            # 返回当前节点高度
            return 1 + max(left_h, right_h)
        dfs(root)
        return max_dia

注：问题配套附件包含题目原文截图、报错用例截图，可对照上述反例场景查看报错用例的树结构验证逻辑正确性。

内容的提问来源于stack exchange，提问作者mkj4332