LeetCode 543. 二叉树的直径 详细技术解析

LeetCode 543. 二叉树的直径 详细技术解析本文针对 LeetCode 543. 二叉树的直径 问题从题目解析、核心思路、代码实现、边界处理到面试拓展进行全方位拆解适合算法入门及进阶开发者阅读附完整可运行代码、测试案例及避坑指南。一、题目核心解析1.1 题目描述精准版给定一棵二叉树的根节点 root返回该树的直径。二叉树的直径定义为树中任意两个节点之间最长路径的长度路径长度由两个节点之间的边数表示。这条路径可能经过根节点也可能不经过根节点。1.2 关键信息提炼避坑重点核心定义直径是「边数」不是节点数易错点比如路径 [4,2,1,3] 有3条边直径为3而非4个节点路径特性最长路径必然是某一个节点的「左子树最大深度 右子树最大深度」因为路径是两个叶子节点之间的连线中间会经过一个“中转节点”遍历要求需要遍历每个节点计算其左右子树深度之和记录最大值即为二叉树的直径数据范围节点数 1~10⁴时间复杂度需控制在 O(n)n为节点数否则会超时边界场景树只有1个节点直径0、树只有2个节点直径1、斜树所有节点只有左/右子树直径为节点数-1。1.3 示例拆解直观理解直径含义示例 1输入root [1,2,3,4,5]二叉树结构如下 1 / \ 2 3 / \ 4 5 解析 1. 遍历每个节点计算其左右子树深度之和 - 节点4左0 右0 0 - 节点5左0 右0 0 - 节点2左14的深度 右15的深度 2 - 节点3左0 右0 0 - 节点1左22的深度 右13的深度 3 2. 最大值为3即为二叉树的直径路径 [4,2,1,3] 或 [5,2,1,3]均为3条边。 输出3示例 2输入root [1,2]二叉树结构如下 1 / 2 解析 1. 遍历节点 - 节点2左右深度和为0 - 节点1左12的深度 右0 1 2. 最大值为1即为直径路径 [2,1]1条边。 输出1二、解题思路拆解从原理到实现本题的核心是「找到所有节点的左右子树深度之和的最大值」因为二叉树的最长路径本质上是某一个节点的左子树最深节点到右子树最深节点的连线这条连线的边数就是该节点的左右子树深度之和。2.1 核心思路后序遍历采用「后序遍历」左→右→根原因如下要计算一个节点的左右子树深度必须先计算其左、右子节点的深度后序遍历先处理子节点再处理父节点遍历每个节点时同步计算「当前节点左右子树深度之和」并与全局最大值比较更新直径每个节点只遍历一次时间复杂度 O(n)满足 10⁴ 节点的性能要求。2.2 具体步骤初始化一个全局变量或类成员变量用于记录直径的最大值初始值为0定义一个递归函数用于计算某个节点的最大深度同时在函数内部计算该节点的左右子树深度之和更新全局最大值递归终止条件当节点为None时返回深度0空节点的深度为0递归逻辑计算左子树的最大深度 left_depth计算右子树的最大深度 right_depth更新直径最大值当前节点的左右深度之和left_depth right_depth与全局最大值比较取较大值返回当前节点的最大深度1 max(left_depth, right_depth)当前节点本身占1层加上左右子树中较深的一层。调用递归函数从根节点开始计算最终返回全局最大值即为二叉树的直径。2.3 常见误区避坑指南误区1将「节点数」当作「边数」比如示例1中误将4个节点当作直径4实际是3条边误区2只计算根节点的左右子树深度之和忽略了“最长路径不经过根节点”的情况比如一棵左子树有深层分支右子树较浅最长路径可能在左子树内部误区3递归时忘记返回当前节点的深度导致后续计算错误误区4全局最大值未初始化或未及时更新导致最终结果错误。三、完整代码实现贴合题目要求格式代码严格按照题目要求的类和方法格式编写添加详细注释兼顾可读性和正确性可直接复制到 LeetCode 提交通过适配Python3环境处理了所有边界场景。# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defdiameterOfBinaryTree(self,root:Optional[TreeNode])-int: 计算二叉树的直径 :param root: 二叉树的根节点 :return: 二叉树的直径最长路径的边数 # 初始化全局最大值记录直径用列表实现“可变对象”避免递归中无法修改self.max_diameter0defmax_depth(node:Optional[TreeNode])-int:辅助递归函数计算当前节点的最大深度并更新直径最大值# 终止条件空节点深度为0ifnotnode:return0# 后序遍历先计算左、右子树深度left_depthmax_depth(node.left)right_depthmax_depth(node.right)# 关键更新直径最大值当前节点的左右子树深度之和self.max_diametermax(self.max_diameter,left_depthright_depth)# 返回当前节点的最大深度自身1层 左右子树较深的一层return1max(left_depth,right_depth)# 从根节点开始计算深度同步更新直径max_depth(root)# 返回最终的直径最大值returnself.max_diameter代码说明关键细节self.max_diameter类成员变量用于记录直径最大值递归过程中持续更新max_depth 函数既负责计算节点深度又负责更新直径一举两得避免重复遍历终止条件空节点返回0符合二叉树深度的定义时间复杂度O(n)每个节点仅遍历一次空间复杂度O(h)h为二叉树的高度递归栈深度最坏情况斜树hn最好情况平衡树hlogn。代码调用示例与题目示例一致# 示例1构造二叉树 [1,2,3,4,5]root1TreeNode(1)root1.leftTreeNode(2)root1.rightTreeNode(3)root1.left.leftTreeNode(4)root1.left.rightTreeNode(5)solutionSolution()print(solution.diameterOfBinaryTree(root1))# 输出3# 示例2构造二叉树 [1,2]root2TreeNode(1)root2.leftTreeNode(2)print(solution.diameterOfBinaryTree(root2))# 输出1四、测试案例与边界情况分析为确保代码鲁棒性梳理5种常见边界场景逐一测试验证覆盖所有易错情况。4.1 边界情况1树只有1个节点输入root [1] 解析只有一个节点没有边直径为0 输出04.2 边界情况2斜树所有节点只有左子树输入root [1,2,null,3,null,4,null,5]结构如下 1 / 2 / 3 / 4 / 5 解析最长路径为 [5,4,3,2,1]共4条边 输出44.3 边界情况3斜树所有节点只有右子树输入root [1,null,2,null,3,null,4] 解析最长路径为 [1,2,3,4]共3条边 输出34.4 边界情况4平衡树最长路径不经过根节点输入root [1,2,3,4,5,null,null,6,7]结构如下 1 / \ 2 3 / \ 4 5 / \ 6 7 解析最长路径为 [6,4,2,5]共3条边不经过根节点1 输出34.5 边界情况5满二叉树深度为3输入root [1,2,3,4,5,6,7] 解析最长路径为 [4,2,5] 或 [6,3,7]均为2条边不实际最长路径为 [4,2,1,3,7]共4条边 输出4五、复杂度总结与面试提示5.1 复杂度总结时间复杂度O(n)n为二叉树的节点数每个节点仅被遍历一次效率最优空间复杂度O(h)h为二叉树的高度递归栈的深度取决于树的高度最坏情况斜树hn最好情况平衡树hlogn均满足题目数据范围要求。5.2 面试提示重点本题核心考点后序遍历的应用、二叉树深度计算、全局变量的使用或用列表实现可变对象面试高频提问1为什么用后序遍历答因为需要先获取左右子树的深度才能计算当前节点的左右深度之和进而更新直径面试高频提问2如果不使用全局变量如何实现答可以用列表可变对象存储最大值或在递归函数中返回「当前深度」和「当前直径最大值」层层向上传递面试高频提问3如何处理10⁴个节点的极端情况答代码时间复杂度O(n)无超时风险递归栈深度最坏为10⁴Python默认递归深度限制为1000需注意可通过sys.setrecursionlimit调整但实际面试中无需主动提及除非面试官追问易错点强调直径是「边数」不是「节点数」必须遍历所有节点不能只计算根节点的左右深度之和。六、拓展思路进阶优化6.1 非递归实现避免递归栈溢出当二叉树高度极大如10⁴层的斜树递归会导致栈溢出此时可采用「后序遍历的非递归实现」用栈模拟递归核心思路不变只是将递归改为迭代代码略复杂但稳定性更高。6.2 不使用全局变量的实现方式通过递归函数返回两个值当前节点深度、当前子树的直径最大值避免使用全局变量代码更严谨适合面试中展示代码功底示例如下核心片段defdiameterOfBinaryTree(self,root:Optional[TreeNode])-int:defdfs(node):ifnotnode:return0,0# (当前深度当前子树直径)left_depth,left_diadfs(node.left)right_depth,right_diadfs(node.right)# 当前节点的直径候选左右深度之和current_dialeft_depthright_depth# 子树直径最大值当前候选、左子树直径、右子树直径的最大值max_diamax(current_dia,left_dia,right_dia)# 返回当前深度和子树直径最大值return1max(left_depth,right_depth),max_dia _,max_diadfs(root)returnmax_dia七、总结本题是二叉树遍历的经典应用题难度中等核心在于理解「直径的本质是节点左右子树深度之和的最大值」关键是通过后序遍历高效计算每个节点的深度并同步更新直径最大值。代码实现的核心是「后序遍历全局最大值记录」逻辑简洁、效率最优适合面试时快速写出正确答案。同时掌握边界情况和常见误区能有效提升代码鲁棒性避免因细节问题导致WA。如果需要进一步拓展如非递归实现、多叉树直径计算可留言讨论共同完善解题方案。