企业官网建设流程全解析

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函数共同的数学基础。

两种解法的本质区别在于遍历顺序与是否剪枝：

二、方法一：后序遍历 + 剪枝（自底向上）

此方法是本题的最优解法，但剪枝的方法不易第一时间想到。

2.1 算法思路

对二叉树做后序遍历，从底至顶返回子树深度。在自底向上的过程中，一旦判定某棵子树不是平衡树，就"剪枝"——直接向上返回特殊标记 $-1$，不再继续计算，从而在发现失衡的第一时间终止递归。

2.2 算法流程

函数recur(root)：

• 返回值：
  1. 当节点root的左 / 右子树深度差 $\leq 1$：返回当前子树的深度，即max(left, right) + 1；
  2. 当节点root的左 / 右子树深度差 $> 1$：返回 $-1$，代表此子树不是平衡树。
• 终止条件：
  1. 当root为空：说明越过叶节点，返回高度 $0$；
  2. 当左（右）子树深度为 $-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) != -1

class 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。
• 返回值：所有子树都需要满足平衡树性质，因此以下三者使用与逻辑&&连接：
  1. abs(depth(root.left) - depth(root.right)) <= 1：判断当前子树是否是平衡树；
  2. isBalanced(root.left)：先序遍历递归，判断当前子树的左子树是否是平衡树；
  3. 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)) + 1

class 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(N+1)$ 层；
  • 通过调用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{N+1}{2}$，因此各层执行depth(root)的时间复杂度均为 $O(N)$（每层开始，最多遍历 $N$ 个节点，最少遍历 $\frac{N+1}{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对应方法二）：

• Python：lc_110_balanced_binary_tree_s1.py 与 lc_110_balanced_binary_tree_s2.py
• Java：lc_110_balanced_binary_tree_s1.java 与 lc_110_balanced_binary_tree_s2.java
• C++：lc_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。

五、两种解法的取舍与面试要点

面试建议：先口述方法二建立直观认识，再过渡到方法一说明优化点（剪枝 + 消除重复计算），最后给出复杂度对比，这是此类树形递归题的经典答题路径。需要注意方法一的返回值是"深度或 -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