LeetCode 110. 平衡二叉树 详细技术解析

LeetCode 110. 平衡二叉树 详细技术解析**标签**LeetCode | 二叉树 | 平衡二叉树 | 深度优先遍历 | 递归 | 简单难度**核心考点**平衡二叉树的定义、二叉树深度计算、递归与迭代遍历的应用、剪枝优化**适用人群**算法初学者、二叉树入门学习者、面试备战者重点掌握递归剪枝思想**前置说明**本文将从题目拆解、核心定义、思路推导递归迭代两种方案、代码实现含详细注释、复杂度分析、边界案例、常见坑点七个维度完整解析本题解决方案确保新手能看懂、老手能复用重点突破“平衡判断”与“深度计算”的联动优化贴合题目要求的代码格式。一、题目深度解析1.1 题目大意给定一棵二叉树的根节点 root判断这棵二叉树是否为平衡二叉树。若为平衡二叉树返回 true否则返回 false。1.2 核心定义平衡二叉树本题的核心是理解平衡二叉树的严格定义必须同时满足两个条件树的每一个节点的左、右两个子树的高度差的绝对值 ≤ 1该节点的左子树和右子树也必须分别是平衡二叉树递归定义。注意仅判断根节点的左右子树高度差是不够的必须确保所有子节点都满足条件如示例2根节点左右子树高度差为1但左子树自身不平衡因此整体不是平衡二叉树。1.3 示例拆解帮助理解示例1输入 root [3,9,20,null,null,15,7]树的结构根节点3左子树为9叶子节点右子树为20左孩子15右孩子7均为叶子节点高度计算根节点左子树高度1右子树高度2高度差1 ≤ 1所有子节点9、20、15、7均满足平衡条件结论返回 true。示例2输入 root [1,2,2,3,3,null,null,4,4]树的结构根节点1左子树2左孩子3右孩子3右子树2无孩子左子树的左孩子3还有两个孩子4高度计算根节点左子树高度3右子树高度1高度差2 1且左子树的左孩子3的左右子树高度差为0但它的父节点左子树2的左右子树高度差为2已不满足条件结论返回 false。示例3输入 root []空树根据平衡二叉树的定义空树属于平衡二叉树无节点自然满足所有条件结论返回 true。二、解题思路推导从基础到优化2.1 核心思路高度计算 平衡判断平衡二叉树的判断依赖“二叉树高度”的计算核心逻辑是对每个节点计算其左、右子树的高度判断高度差是否≤1同时递归判断左、右子树是否也为平衡二叉树。衍生出两种解题方案基础递归先算高度再判断存在重复计算、优化递归剪枝边算高度边判断避免重复以及迭代方案适配递归栈溢出场景。2.2 方案1基础递归易懂但低效思路分为两步分开实现编写一个辅助函数计算二叉树的高度从当前节点到叶子节点的最长路径长度叶子节点高度为1空节点高度为0递归判断当前节点的左右子树高度差是否≤1同时递归判断左子树和右子树是否平衡。问题存在大量重复计算。例如计算根节点高度时会递归计算左、右子树高度判断左子树是否平衡时又会再次计算左子树的高度时间复杂度较高。2.3 方案2优化递归剪枝推荐核心优化将“高度计算”和“平衡判断”合并到一个递归函数中边计算高度边判断平衡。若某一子树不平衡直接返回一个特殊值如-1上层递归收到特殊值后无需继续计算直接返回-1剪枝避免重复计算。具体逻辑递归函数返回值若当前子树平衡返回当前子树的高度若不平衡返回-1递归终止条件空节点返回0高度为0递归过程计算左子树的高度若左子树不平衡返回-1直接返回-1计算右子树的高度若右子树不平衡返回-1直接返回-1判断当前节点的左右子树高度差是否1若是返回-1不平衡否则返回当前子树高度max(左高度, 右高度) 1。最终判断若递归函数返回值为-1说明树不平衡否则平衡。2.4 方案3迭代方案避免递归栈溢出思路使用后序遍历左→右→根遍历二叉树的所有节点对每个节点计算其左右子树的高度判断是否平衡。具体步骤用栈模拟后序遍历记录每个节点的访问状态是否已处理左右子树遍历过程中用哈希表存储每个节点的高度避免重复计算当节点的左右子树均处理完成后取出左右子树的高度判断高度差是否≤1若不满足直接返回false。适用场景当树的深度极大如节点数5000呈链式递归会导致栈溢出此时迭代方案更稳妥。三、完整代码实现含详细注释贴合要求格式重点实现优化递归方案面试高频高效简洁同时提供基础递归和迭代方案作为补充所有代码严格贴合题目要求的类和方法格式可直接复制提交LeetCode兼容Python3环境。3.1 优化递归方案推荐时间复杂度最优# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defisBalanced(self,root:Optional[TreeNode])-bool:# 辅助递归函数返回当前子树的高度若不平衡则返回-1defget_height(node):# 终止条件空节点高度为0且平衡ifnotnode:return0# 递归计算左子树高度若左子树不平衡直接返回-1剪枝left_heightget_height(node.left)ifleft_height-1:return-1# 递归计算右子树高度若右子树不平衡直接返回-1剪枝right_heightget_height(node.right)ifright_height-1:return-1# 判断当前节点的左右子树高度差是否超过1超过则不平衡返回-1ifabs(left_height-right_height)1:return-1# 若平衡返回当前子树的高度当前节点高度 左右子树最大高度 1returnmax(left_height,right_height)1# 若递归函数返回-1说明树不平衡否则平衡returnget_height(root)!-13.2 基础递归方案易懂适合入门# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defisBalanced(self,root:Optional[TreeNode])-bool:# 辅助函数计算当前节点所在子树的高度叶子节点高度为1空节点为0defget_height(node):ifnotnode:return0# 左子树高度leftget_height(node.left)# 右子树高度rightget_height(node.right)# 当前子树高度 左右子树最大高度 1returnmax(left,right)1# 终止条件空树是平衡的ifnotroot:returnTrue# 计算当前节点左右子树高度差left_heightget_height(root.left)right_heightget_height(root.right)# 递归判断当前节点平衡 左子树平衡 右子树平衡returnabs(left_height-right_height)1andself.isBalanced(root.left)andself.isBalanced(root.right)3.3 迭代方案避免递归栈溢出# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defisBalanced(self,root:Optional[TreeNode])-bool:ifnotroot:returnTrue# 栈用于后序遍历存储节点是否已访问stack[(root,False)]# 哈希表存储每个节点的高度避免重复计算height_map{}whilestack:node,visitedstack.pop()ifvisited:# 节点已访问左右子树已处理计算高度并判断平衡left_heightheight_map.get(node.left,0)right_heightheight_map.get(node.right,0)# 若高度差超过1直接返回falseifabs(left_height-right_height)1:returnFalse# 存储当前节点的高度height_map[node]max(left_height,right_height)1else:# 未访问先压入当前节点标记为已访问再压入右、左子节点后序遍历左→右→根stack.append((node,True))ifnode.right:stack.append((node.right,False))ifnode.left:stack.append((node.left,False))# 所有节点均满足平衡条件returnTrue四、代码解析与复杂度分析4.1 核心代码解析优化递归方案辅助函数get_height核心作用是“计算高度判断平衡”二合一实现剪枝优化空节点返回0符合二叉树高度定义先计算左子树高度若左子树不平衡返回-1直接返回-1无需计算右子树剪枝同理计算右子树高度避免无效计算当前节点的高度 左右子树最大高度 1符合二叉树高度计算逻辑。主函数逻辑调用get_height(root)若返回值为-1说明树中存在不平衡的节点返回false否则返回true逻辑简洁高效。4.2 复杂度分析三种方案对比方案时间复杂度空间复杂度优势劣势优化递归O(n)n为节点数每个节点仅访问一次O(h)h为树的高度递归栈深度树高最坏情况hn链式树高效、简洁面试高频极端情况下链式树可能栈溢出基础递归O(n²)最坏情况链式树每个节点都要重复计算子树高度O(h)递归栈深度逻辑简单易于理解效率低不适合大数据量如n5000迭代O(n)每个节点访问两次入栈和出栈O(n)栈和哈希表存储节点信息避免递归栈溢出稳定代码稍复杂可读性不如递归补充题目提示节点数在[0,5000]内优化递归方案完全满足需求且代码简洁是面试中的最优选择。五、边界案例与测试验证5.1 边界案例容易踩坑的场景案例1空树示例3输入root []输出true解析空树无节点满足平衡二叉树定义所有方案均返回true。案例2单节点树输入root [1]输出true解析单节点的左右子树均为空高度差为0满足平衡条件。案例3链式树最坏情况输入root [1,2,null,3,null,4,null,5]输出false解析树呈左链式根节点左子树高度4右子树高度0高度差41不平衡。案例4子节点不平衡示例2输入root [1,2,2,3,3,null,null,4,4]输出false解析根节点左右子树高度差1但左子树的左孩子3的左右子树高度差0其父亲左子树2的左右子树高度差2不满足条件。5.2 测试验证将上述案例代入三种代码方案均可得到正确结果。提交LeetCode后可通过所有测试用例包括节点数5000的极端场景优化递归和迭代方案均能通过基础递归方案会超时。六、常见坑点与避坑指南坑点1误解平衡二叉树定义仅判断根节点错误表现仅计算根节点左右子树高度差忽略子节点的平衡判断如示例2会误判为true避坑必须递归判断所有子节点确保每个节点的左右子树都满足高度差≤1。坑点2二叉树高度计算错误错误表现将叶子节点高度设为0或空节点高度设为1导致高度差计算错误避坑统一高度定义——空节点高度为0叶子节点高度为1非叶子节点高度max(左高度, 右高度)1。坑点3未做剪枝优化导致超时错误表现使用基础递归方案当节点数较多如n5000时超时无法通过避坑优先使用优化递归方案边计算高度边剪枝避免重复计算。坑点4递归终止条件遗漏错误表现未处理空节点导致递归栈溢出避坑递归函数中先判断节点是否为空空节点返回0高度或直接返回true平衡。七、总结与拓展7.1 解题总结本题的核心是“平衡二叉树的定义”和“二叉树高度计算”最优解决方案是优化递归剪枝其核心优势是将高度计算与平衡判断合并避免重复计算时间复杂度O(n)代码简洁易懂是面试中的首选。关键要点平衡二叉树是“全局平衡”而非仅根节点平衡剪枝优化是提升效率的核心避免无效的高度计算二叉树高度的定义必须统一否则会导致判断错误。7.2 拓展思考拓展1如何将一棵不平衡的二叉树转为平衡二叉树思路通过AVL树的旋转操作左旋、右旋、左右旋、右左旋调整节点位置使每个节点的左右子树高度差≤1。拓展2平衡二叉树与完全二叉树、满二叉树的区别满二叉树每一层的节点数都达到最大值一定是平衡二叉树完全二叉树除最后一层外每一层节点数都达到最大值最后一层节点从左到右连续不一定是平衡二叉树如示例2平衡二叉树仅要求每个节点的左右子树高度差≤1不要求节点分布均匀。拓展3迭代方案中为何选择后序遍历思路后序遍历先处理左、右子树再处理当前节点刚好符合“先计算子树高度再判断当前节点平衡”的逻辑。通过本题可重点掌握“递归剪枝”的优化思想以及二叉树高度的计算方法这是二叉树类题目中高频考察的知识点同时也是后续学习AVL树、红黑树等平衡树的基础建议重点掌握优化递归方案。