LeetCode-Book 精讲LeetCode 110 平衡二叉树——后序遍历剪枝与先序遍历判深两种解法详解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读本篇技术指南以 LeetCode-Book 仓库《Krahets 笔面试精选 88 题》中的 110. 平衡二叉树 为核心系统讲解平衡二叉树Balanced Binary Tree的判定方法。文章将围绕一条核心性质展开——当前树的深度等于左子树深度与右子树深度的最大值加 1并给出两种经典解法时间复杂度为 $O(N)$ 的后序遍历 剪枝自底向上最优解以及思路直观但存在重复计算、时间复杂度为 $O(N \log N)$ 的先序遍历 判断深度自顶向下。读完本文你将掌握两种解法的完整算法流程、Python / Java / C 三种语言的参考实现、复杂度推导过程并能在本地直接运行仓库提供的驱动代码验证结果。一、问题定义与核心性质平衡二叉树定义为一棵二叉树中任意节点的左、右子树高度差的绝对值不超过 1。要判断一棵树是否平衡最朴素的想法是逐节点检查对每个节点算出其左子树深度与右子树深度若所有节点都满足abs(left - right) 1则整棵树平衡。而计算深度的依据正是本文的基础性质当前树的深度 max(左子树的深度, 右子树的深度) 1即节点root的深度由其左右子树深度中的较大者递推而来空节点越过叶节点的深度记为 $0$。这一性质是方法一recur函数与方法二depth函数共同的数学基础。两种解法的本质区别在于遍历顺序与是否剪枝对比维度方法一后序遍历 剪枝方法二先序遍历 判断深度遍历方向自底向上后序自顶向下先序深度计算递归返回值中携带只算一遍每访问一个节点都调用depth重复计算是否剪枝子树失衡即返回 -1 提前终止无剪枝全量遍历时间复杂度$O(N)$$O(N \log N)$满二叉树最差空间复杂度$O(N)$$O(N)$特点最优解法但剪枝技巧不易第一时间想到容易想到但存在大量重复计算二、方法一后序遍历 剪枝自底向上此方法是本题的最优解法但剪枝的方法不易第一时间想到。2.1 算法思路对二叉树做后序遍历从底至顶返回子树深度。在自底向上的过程中一旦判定某棵子树不是平衡树就剪枝——直接向上返回特殊标记 $-1$不再继续计算从而在发现失衡的第一时间终止递归。2.2 算法流程函数recur(root)返回值当节点root的左 / 右子树深度差 $\leq 1$返回当前子树的深度即max(left, right) 1当节点root的左 / 右子树深度差 $ 1$返回 $-1$代表此子树不是平衡树。终止条件当root为空说明越过叶节点返回高度 $0$当左右子树深度为 $-1$代表此树的左右子树不是平衡树剪枝直接返回 $-1$。函数isBalanced(root)返回值若recur(root) ! -1则说明此树平衡返回true否则返回false。关键点在于深度为 $-1$ 既是失衡的标记也充当了剪枝的开关。代码中先递归左子树若左子树返回 $-1$ 则立即返回不再递归右子树右子树同理。由于任意节点的深度都不可能为负$-1$ 是一个安全且不会产生歧义的哨兵值。2.3 参考代码class Solution: def isBalanced(self, root: Optional[TreeNode]) - bool: def recur(root): if not root: return 0 left recur(root.left) if left -1: return -1 right recur(root.right) if right -1: return -1 return max(left, right) 1 if abs(left - right) 1 else -1 return recur(root) ! -1class Solution { public boolean isBalanced(TreeNode root) { return recur(root) ! -1; } private int recur(TreeNode root) { if (root null) return 0; int left recur(root.left); if (left -1) return -1; int right recur(root.right); if (right -1) return -1; return Math.abs(left - right) 2 ? Math.max(left, right) 1 : -1; } }class Solution { public: bool isBalanced(TreeNode* root) { return recur(root) ! -1; } private: int recur(TreeNode* root) { if (root nullptr) return 0; int left recur(root-left); if (left -1) return -1; int right recur(root-right); if (right -1) return -1; return abs(left - right) 2 ? max(left, right) 1 : -1; } };2.4 复杂度分析时间复杂度 $O(N)$$N$ 为树的节点数。最差情况下整棵树平衡或仅顶层失衡需要递归遍历树的所有节点每个节点只被访问一次。空间复杂度 $O(N)$最差情况下树退化为链表时系统递归需要使用 $O(N)$ 的栈空间。三、方法二先序遍历 判断深度自顶向下此方法容易想到但会产生大量重复计算时间复杂度较高。3.1 算法思路构造一个计算当前子树深度的函数depth(root)通过比较某子树左右子树的深度差abs(depth(root.left) - depth(root.right)) 1是否成立判断该子树是否平衡。若所有子树都平衡则整棵树平衡。3.2 算法流程函数isBalanced(root)判断树root是否平衡特例处理若树根节点root为空则直接返回true。返回值所有子树都需要满足平衡树性质因此以下三者使用与逻辑连接abs(depth(root.left) - depth(root.right)) 1判断当前子树是否是平衡树isBalanced(root.left)先序遍历递归判断当前子树的左子树是否是平衡树isBalanced(root.right)先序遍历递归判断当前子树的右子树是否是平衡树。函数depth(root)计算树root的深度终止条件当root为空即越过叶子节点返回高度 $0$。返回值返回左 / 右子树的深度的最大值 $1$即max(depth(root.left), depth(root.right)) 1。由于短路求值一旦发现当前节点失衡或某侧子树失衡后续判断会立即停止这在一定程度上缓解了无谓的深度计算但整体仍无法避免对depth的重复调用。3.3 参考代码class Solution: def isBalanced(self, root: Optional[TreeNode]) - bool: if not root: return True return abs(self.depth(root.left) - self.depth(root.right)) 1 and \ self.isBalanced(root.left) and self.isBalanced(root.right) def depth(self, root): if not root: return 0 return max(self.depth(root.left), self.depth(root.right)) 1class Solution { public boolean isBalanced(TreeNode root) { if (root null) return true; return Math.abs(depth(root.left) - depth(root.right)) 1 isBalanced(root.left) isBalanced(root.right); } private int depth(TreeNode root) { if (root null) return 0; return Math.max(depth(root.left), depth(root.right)) 1; } }class Solution { public: bool isBalanced(TreeNode* root) { if (root nullptr) return true; return abs(depth(root-left) - depth(root-right)) 1 isBalanced(root-left) isBalanced(root-right); } private: int depth(TreeNode* root) { if (root nullptr) return 0; return max(depth(root-left), depth(root-right)) 1; } };3.4 复杂度分析时间复杂度 $O(N \log N)$最差情况下为满二叉树时isBalanced(root)遍历树的所有节点而判断每个节点的深度depth(root)又需要遍历各子树的所有节点。推导过程如下满二叉树高度的复杂度为 $O(\log N)$将满二叉树按层分为 $\log(N1)$ 层通过调用depth(root)判断各层节点的对应子树深度各层需遍历的节点数量为 $N \times 1$、$\frac{N-1}{2} \times 2$、$\frac{N-3}{4} \times 4$、$\frac{N-7}{8} \times 8$、…、$1 \times \frac{N1}{2}$因此各层执行depth(root)的时间复杂度均为 $O(N)$每层开始最多遍历 $N$ 个节点最少遍历 $\frac{N1}{2}$ 个节点。其中 $\frac{N-3}{4} \times 4$ 表示从此层开始总共需遍历 $N-3$ 个节点该层共有 $4$ 个节点每个子树需遍历 $\frac{N-3}{4}$ 个节点因此总体时间复杂度 $$ 每层执行复杂度 $\times$ 层数复杂度 $ O(N \times \log N)$。空间复杂度 $O(N)$最差情况下树退化为链表时系统递归需要使用 $O(N)$ 的栈空间。四、仓库源码印证与本地运行验证本文对应的解法在仓库中均有可直接运行的多语言实现文件名与文档中的方法一一对应s1对应方法一s2对应方法二Pythonlc_110_balanced_binary_tree_s1.py 与 lc_110_balanced_binary_tree_s2.pyJavalc_110_balanced_binary_tree_s1.java 与 lc_110_balanced_binary_tree_s2.javaClc_110_balanced_binary_tree_s1.cpp 与 lc_110_balanced_binary_tree_s2.cpp以 lc_110_balanced_binary_tree_s1.cpp 为例其Solution类与文档代码完全一致并附带了完整的测试与驱动代码#include ../include/include.hpp // Solution Code class Solution { public: bool isBalanced(TreeNode* root) { return recur(root) ! -1; } private: int recur(TreeNode* root) { if (root nullptr) return 0; int left recur(root-left); if (left -1) return -1; int right recur(root-right); if (right -1) return -1; return abs(left - right) 2 ? max(left, right) 1 : -1; } }; int main() { // Test Case TreeNode* root vectorToTree({3, 9, 20, INT_MAX, INT_MAX, 15, 7}); // Driver Code Solution* slt new Solution(); bool res slt-isBalanced(root); cout (res ? true : false) endl; return 0; }4.1 测试用例解析仓库三种语言采用了完全相同的测试用例层序遍历序列null/INT_MAX表示空节点[3, 9, 20, null, null, 15, 7]对应的二叉树结构为3 / \ 9 20 / \ 15 7验证过程根节点 3 的左子树节点 9深度为 1右子树节点 20含 15、7 两个孩子深度为 2深度差 $|1 - 2| 1 \leq 1$其余节点均为叶节点或高度差为 0 的内部节点全部满足平衡条件因此该用例输出true。运行三个语言的驱动代码均可得到该结果。作为对照读者可将测试用例替换为经典的失衡树[1, 2, 2, 3, 3, null, null, 4, 4]其左子树 2 → 3 → 4 形成单链高度为 3右子树高度为 1深度差为 2观察方法一在到达第三层时即因left -1剪枝返回而方法二则会对每个节点重复调用depth——这正是两种方法复杂度差异的直观体现。4.2 运行方式Python直接执行python lc_110_balanced_binary_tree_s1.py输出true。文件中from include import *引入了仓库 include 目录下封装的TreeNode、list_to_tree等工具。Java类位于lc_110_balanced_binary_tree包下通过TreeNode.arrToTree(new Integer[]{3, 9, 20, null, null, 15, 7})构造测试树main方法输出结果。C包含 include.hpp其内部进一步引用 TreeNode.hpp 等头文件通过vectorToTree构造测试树编译运行后输出true。五、两种解法的取舍与面试要点要点方法一后序 剪枝方法二先序 判深核心思想自底向上一次遍历同时完成求深度与判平衡自顶向下先判当前节点再递归子树重复计算无深度信息在返回值中天然复用有高层节点会重复计算低层子树的深度最差时间复杂度$O(N)$$O(N \log N)$编码难度需理解 $-1$ 哨兵与剪枝时机稍难思路直白先写depth再写isBalanced即可适合场景面试推荐答案、追求最优解快速 AC、作为推导最优解的铺垫面试建议先口述方法二建立直观认识再过渡到方法一说明优化点剪枝 消除重复计算最后给出复杂度对比这是此类树形递归题的经典答题路径。需要注意方法一的返回值是深度或 -1的双重含义设计isBalanced只关心最终返回值是否为 $-1$。六、关联题目与延伸阅读LeetCode 110 与剑指 Offer 55 - II 为同一题仓库中亦收录了对应内容可供交叉阅读剑指 Offer 版本文档剑指 Offer 55 - II. 平衡二叉树其实现位于 sfo_55ii_balanced_binary_tree 系列目录LeetCode 题库LCR 版对应题解LCR 176. 判断是否为平衡二叉树与本题深度递归 剪枝同构的基础题104. 二叉树的最大深度可先掌握深度计算的递归写法再回到本题。掌握用返回值携带附加语义深度 or 哨兵这一技巧后它同样适用于判断对称二叉树、路径总和等需要自底向上聚合信息的题目是树类递归题中复用率极高的套路。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 精讲：LeetCode 110 平衡二叉树——后序遍历剪枝与先序遍历判深两种解法详解
LeetCode-Book 精讲LeetCode 110 平衡二叉树——后序遍历剪枝与先序遍历判深两种解法详解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读本篇技术指南以 LeetCode-Book 仓库《Krahets 笔面试精选 88 题》中的 110. 平衡二叉树 为核心系统讲解平衡二叉树Balanced Binary Tree的判定方法。文章将围绕一条核心性质展开——当前树的深度等于左子树深度与右子树深度的最大值加 1并给出两种经典解法时间复杂度为 $O(N)$ 的后序遍历 剪枝自底向上最优解以及思路直观但存在重复计算、时间复杂度为 $O(N \log N)$ 的先序遍历 判断深度自顶向下。读完本文你将掌握两种解法的完整算法流程、Python / Java / C 三种语言的参考实现、复杂度推导过程并能在本地直接运行仓库提供的驱动代码验证结果。一、问题定义与核心性质平衡二叉树定义为一棵二叉树中任意节点的左、右子树高度差的绝对值不超过 1。要判断一棵树是否平衡最朴素的想法是逐节点检查对每个节点算出其左子树深度与右子树深度若所有节点都满足abs(left - right) 1则整棵树平衡。而计算深度的依据正是本文的基础性质当前树的深度 max(左子树的深度, 右子树的深度) 1即节点root的深度由其左右子树深度中的较大者递推而来空节点越过叶节点的深度记为 $0$。这一性质是方法一recur函数与方法二depth函数共同的数学基础。两种解法的本质区别在于遍历顺序与是否剪枝对比维度方法一后序遍历 剪枝方法二先序遍历 判断深度遍历方向自底向上后序自顶向下先序深度计算递归返回值中携带只算一遍每访问一个节点都调用depth重复计算是否剪枝子树失衡即返回 -1 提前终止无剪枝全量遍历时间复杂度$O(N)$$O(N \log N)$满二叉树最差空间复杂度$O(N)$$O(N)$特点最优解法但剪枝技巧不易第一时间想到容易想到但存在大量重复计算二、方法一后序遍历 剪枝自底向上此方法是本题的最优解法但剪枝的方法不易第一时间想到。2.1 算法思路对二叉树做后序遍历从底至顶返回子树深度。在自底向上的过程中一旦判定某棵子树不是平衡树就剪枝——直接向上返回特殊标记 $-1$不再继续计算从而在发现失衡的第一时间终止递归。2.2 算法流程函数recur(root)返回值当节点root的左 / 右子树深度差 $\leq 1$返回当前子树的深度即max(left, right) 1当节点root的左 / 右子树深度差 $ 1$返回 $-1$代表此子树不是平衡树。终止条件当root为空说明越过叶节点返回高度 $0$当左右子树深度为 $-1$代表此树的左右子树不是平衡树剪枝直接返回 $-1$。函数isBalanced(root)返回值若recur(root) ! -1则说明此树平衡返回true否则返回false。关键点在于深度为 $-1$ 既是失衡的标记也充当了剪枝的开关。代码中先递归左子树若左子树返回 $-1$ 则立即返回不再递归右子树右子树同理。由于任意节点的深度都不可能为负$-1$ 是一个安全且不会产生歧义的哨兵值。2.3 参考代码class Solution: def isBalanced(self, root: Optional[TreeNode]) - bool: def recur(root): if not root: return 0 left recur(root.left) if left -1: return -1 right recur(root.right) if right -1: return -1 return max(left, right) 1 if abs(left - right) 1 else -1 return recur(root) ! -1class Solution { public boolean isBalanced(TreeNode root) { return recur(root) ! -1; } private int recur(TreeNode root) { if (root null) return 0; int left recur(root.left); if (left -1) return -1; int right recur(root.right); if (right -1) return -1; return Math.abs(left - right) 2 ? Math.max(left, right) 1 : -1; } }class Solution { public: bool isBalanced(TreeNode* root) { return recur(root) ! -1; } private: int recur(TreeNode* root) { if (root nullptr) return 0; int left recur(root-left); if (left -1) return -1; int right recur(root-right); if (right -1) return -1; return abs(left - right) 2 ? max(left, right) 1 : -1; } };2.4 复杂度分析时间复杂度 $O(N)$$N$ 为树的节点数。最差情况下整棵树平衡或仅顶层失衡需要递归遍历树的所有节点每个节点只被访问一次。空间复杂度 $O(N)$最差情况下树退化为链表时系统递归需要使用 $O(N)$ 的栈空间。三、方法二先序遍历 判断深度自顶向下此方法容易想到但会产生大量重复计算时间复杂度较高。3.1 算法思路构造一个计算当前子树深度的函数depth(root)通过比较某子树左右子树的深度差abs(depth(root.left) - depth(root.right)) 1是否成立判断该子树是否平衡。若所有子树都平衡则整棵树平衡。3.2 算法流程函数isBalanced(root)判断树root是否平衡特例处理若树根节点root为空则直接返回true。返回值所有子树都需要满足平衡树性质因此以下三者使用与逻辑连接abs(depth(root.left) - depth(root.right)) 1判断当前子树是否是平衡树isBalanced(root.left)先序遍历递归判断当前子树的左子树是否是平衡树isBalanced(root.right)先序遍历递归判断当前子树的右子树是否是平衡树。函数depth(root)计算树root的深度终止条件当root为空即越过叶子节点返回高度 $0$。返回值返回左 / 右子树的深度的最大值 $1$即max(depth(root.left), depth(root.right)) 1。由于短路求值一旦发现当前节点失衡或某侧子树失衡后续判断会立即停止这在一定程度上缓解了无谓的深度计算但整体仍无法避免对depth的重复调用。3.3 参考代码class Solution: def isBalanced(self, root: Optional[TreeNode]) - bool: if not root: return True return abs(self.depth(root.left) - self.depth(root.right)) 1 and \ self.isBalanced(root.left) and self.isBalanced(root.right) def depth(self, root): if not root: return 0 return max(self.depth(root.left), self.depth(root.right)) 1class Solution { public boolean isBalanced(TreeNode root) { if (root null) return true; return Math.abs(depth(root.left) - depth(root.right)) 1 isBalanced(root.left) isBalanced(root.right); } private int depth(TreeNode root) { if (root null) return 0; return Math.max(depth(root.left), depth(root.right)) 1; } }class Solution { public: bool isBalanced(TreeNode* root) { if (root nullptr) return true; return abs(depth(root-left) - depth(root-right)) 1 isBalanced(root-left) isBalanced(root-right); } private: int depth(TreeNode* root) { if (root nullptr) return 0; return max(depth(root-left), depth(root-right)) 1; } };3.4 复杂度分析时间复杂度 $O(N \log N)$最差情况下为满二叉树时isBalanced(root)遍历树的所有节点而判断每个节点的深度depth(root)又需要遍历各子树的所有节点。推导过程如下满二叉树高度的复杂度为 $O(\log N)$将满二叉树按层分为 $\log(N1)$ 层通过调用depth(root)判断各层节点的对应子树深度各层需遍历的节点数量为 $N \times 1$、$\frac{N-1}{2} \times 2$、$\frac{N-3}{4} \times 4$、$\frac{N-7}{8} \times 8$、…、$1 \times \frac{N1}{2}$因此各层执行depth(root)的时间复杂度均为 $O(N)$每层开始最多遍历 $N$ 个节点最少遍历 $\frac{N1}{2}$ 个节点。其中 $\frac{N-3}{4} \times 4$ 表示从此层开始总共需遍历 $N-3$ 个节点该层共有 $4$ 个节点每个子树需遍历 $\frac{N-3}{4}$ 个节点因此总体时间复杂度 $$ 每层执行复杂度 $\times$ 层数复杂度 $ O(N \times \log N)$。空间复杂度 $O(N)$最差情况下树退化为链表时系统递归需要使用 $O(N)$ 的栈空间。四、仓库源码印证与本地运行验证本文对应的解法在仓库中均有可直接运行的多语言实现文件名与文档中的方法一一对应s1对应方法一s2对应方法二Pythonlc_110_balanced_binary_tree_s1.py 与 lc_110_balanced_binary_tree_s2.pyJavalc_110_balanced_binary_tree_s1.java 与 lc_110_balanced_binary_tree_s2.javaClc_110_balanced_binary_tree_s1.cpp 与 lc_110_balanced_binary_tree_s2.cpp以 lc_110_balanced_binary_tree_s1.cpp 为例其Solution类与文档代码完全一致并附带了完整的测试与驱动代码#include ../include/include.hpp // Solution Code class Solution { public: bool isBalanced(TreeNode* root) { return recur(root) ! -1; } private: int recur(TreeNode* root) { if (root nullptr) return 0; int left recur(root-left); if (left -1) return -1; int right recur(root-right); if (right -1) return -1; return abs(left - right) 2 ? max(left, right) 1 : -1; } }; int main() { // Test Case TreeNode* root vectorToTree({3, 9, 20, INT_MAX, INT_MAX, 15, 7}); // Driver Code Solution* slt new Solution(); bool res slt-isBalanced(root); cout (res ? true : false) endl; return 0; }4.1 测试用例解析仓库三种语言采用了完全相同的测试用例层序遍历序列null/INT_MAX表示空节点[3, 9, 20, null, null, 15, 7]对应的二叉树结构为3 / \ 9 20 / \ 15 7验证过程根节点 3 的左子树节点 9深度为 1右子树节点 20含 15、7 两个孩子深度为 2深度差 $|1 - 2| 1 \leq 1$其余节点均为叶节点或高度差为 0 的内部节点全部满足平衡条件因此该用例输出true。运行三个语言的驱动代码均可得到该结果。作为对照读者可将测试用例替换为经典的失衡树[1, 2, 2, 3, 3, null, null, 4, 4]其左子树 2 → 3 → 4 形成单链高度为 3右子树高度为 1深度差为 2观察方法一在到达第三层时即因left -1剪枝返回而方法二则会对每个节点重复调用depth——这正是两种方法复杂度差异的直观体现。4.2 运行方式Python直接执行python lc_110_balanced_binary_tree_s1.py输出true。文件中from include import *引入了仓库 include 目录下封装的TreeNode、list_to_tree等工具。Java类位于lc_110_balanced_binary_tree包下通过TreeNode.arrToTree(new Integer[]{3, 9, 20, null, null, 15, 7})构造测试树main方法输出结果。C包含 include.hpp其内部进一步引用 TreeNode.hpp 等头文件通过vectorToTree构造测试树编译运行后输出true。五、两种解法的取舍与面试要点要点方法一后序 剪枝方法二先序 判深核心思想自底向上一次遍历同时完成求深度与判平衡自顶向下先判当前节点再递归子树重复计算无深度信息在返回值中天然复用有高层节点会重复计算低层子树的深度最差时间复杂度$O(N)$$O(N \log N)$编码难度需理解 $-1$ 哨兵与剪枝时机稍难思路直白先写depth再写isBalanced即可适合场景面试推荐答案、追求最优解快速 AC、作为推导最优解的铺垫面试建议先口述方法二建立直观认识再过渡到方法一说明优化点剪枝 消除重复计算最后给出复杂度对比这是此类树形递归题的经典答题路径。需要注意方法一的返回值是深度或 -1的双重含义设计isBalanced只关心最终返回值是否为 $-1$。六、关联题目与延伸阅读LeetCode 110 与剑指 Offer 55 - II 为同一题仓库中亦收录了对应内容可供交叉阅读剑指 Offer 版本文档剑指 Offer 55 - II. 平衡二叉树其实现位于 sfo_55ii_balanced_binary_tree 系列目录LeetCode 题库LCR 版对应题解LCR 176. 判断是否为平衡二叉树与本题深度递归 剪枝同构的基础题104. 二叉树的最大深度可先掌握深度计算的递归写法再回到本题。掌握用返回值携带附加语义深度 or 哨兵这一技巧后它同样适用于判断对称二叉树、路径总和等需要自底向上聚合信息的题目是树类递归题中复用率极高的套路。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考