平衡二叉树的判定：回溯法的深度解析与迭代法拓展
一、题目解析：平衡二叉树的定义与判定条件
题目描述
给定一棵二叉树，判断它是否是平衡二叉树。平衡二叉树的定义是：每个节点的左右子树的高度差的绝对值不超过 1，且左右子树本身也必须是平衡二叉树。
核心条件拆解
- 每个节点的平衡性：左右子树高度差 ≤ 1。
- 子树的递归平衡性：每个子树也必须满足平衡条件。
这意味着我们需要从底向上递归检查每个节点的平衡性，避免冗余计算。
二、回溯法（递归）核心实现：后序遍历的巧妙应用
代码实现
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}public static int getHeight(TreeNode root) {if (root == null) {return 0; // 空树高度为0}int leftHeight = getHeight(root.left);if (leftHeight == -1) { // 左子树不平衡，直接返回-1return -1;}int rightHeight = getHeight(root.right);if (rightHeight == -1) { // 右子树不平衡，直接返回-1return -1;}if (Math.abs(leftHeight - rightHeight) > 1) { // 当前节点不平衡return -1;}return Math.max(leftHeight, rightHeight) + 1; // 返回当前子树高度}
}
核心逻辑：后序遍历+剪枝优化
1. 递归终止条件
- 若当前节点为空，返回高度
0。 - 空树被视为平衡树的基础情况。
2. 后序遍历顺序
- 先递归计算左子树高度，再递归计算右子树高度，最后处理当前节点。
这确保了在检查当前节点平衡性时，左右子树的平衡性已被提前验证。
3. 剪枝优化（-1的传递）
- 若左子树或右子树返回
-1，说明子树不平衡，直接向上传递-1，避免无效计算。
这种“短路”机制将时间复杂度从O(n²)优化至O(n)。
4. 高度计算与平衡判断
- 计算左右子树高度差，若超过1则返回
-1，否则返回当前子树高度（max(左, 右) + 1）。
递归流程模拟：以不平衡树为例
树结构：
1/ \2 3/
4
-
递归计算左子树（节点2）：
- 左子树（节点4）高度为1，右子树为空（高度0）。
- 节点2的左右高度差为
1-0=1，平衡，返回高度2。
-
递归计算右子树（节点3）：
- 左右子树均为空，高度为1，平衡。
-
处理根节点（节点1）：
- 左子树高度2，右子树高度1，差为1，平衡？
- 错误！ 实际左子树的左子树高度为1，右子树高度为0，差为1，平衡。但根节点的左右子树差为1，仍平衡？
- 关键纠正：此例实际平衡，但假设左子树高度为3，右子树高度为1，差为2，则根节点返回-1。
三、回溯法的优缺点分析
| 优点 | 缺点 |
|---|---|
| 代码简洁，逻辑清晰，天然符合递归定义 | 递归深度可能过大（如退化为链表时，栈深度O(n)，可能导致栈溢出） |
| 剪枝优化后时间复杂度O(n) | 空间复杂度依赖递归栈深度，最坏O(n) |
四、大厂面试视角：是否需要迭代法？
大厂考察要点
- 递归的理解深度：能否清晰阐述递归流程、终止条件、时间复杂度。
- 迭代法实现能力：当树深度较大时，递归可能引发栈溢出，需用迭代法手动管理栈。
- 优化意识：能否在递归基础上提出优化方案（如尾递归优化，但Java不支持）。
迭代法必要性分析
- 需要迭代法的场景：
- 题目明确要求非递归实现。
- 处理大规模数据（如百万级节点），避免栈溢出。
- 递归法的适用场景：
- 代码简洁性优先，数据规模较小。
结论：大厂面试中，递归法是基础，但掌握迭代法能体现更全面的工程能力。
五、迭代法实现：后序遍历模拟递归
核心思路
使用栈模拟递归的后序遍历，手动记录每个节点的高度。通过标记节点是否已访问，确保在处理当前节点时，左右子树已被处理完毕。
代码实现
import java.util.Stack;class Solution {public boolean isBalanced(TreeNode root) {if (root == null) return true;Stack<TreeNode> stack = new Stack<>();Stack<Integer> heightStack = new Stack<>();TreeNode prev = null; // 记录上一个访问的节点（后序遍历辅助）int currentHeight = 0;while (root != null || !stack.isEmpty()) {// 遍历到左最深处while (root != null) {stack.push(root);heightStack.push(1); // 初始高度为1（自身）root = root.left;}root = stack.pop();currentHeight = heightStack.pop();// 若有右子树且未被访问（prev不是右子节点），则重新入栈右子树if (root.right != null && prev != root.right) {stack.push(root);heightStack.push(currentHeight + 1); // 右子树高度为当前高度+1？root = root.right;} else {// 处理当前节点（后序遍历）int leftHeight = (root.left != null) ? getStoredHeight(stack, heightStack, root.left) : 0;int rightHeight = (root.right != null) ? getStoredHeight(stack, heightStack, root.right) : 0;if (Math.abs(leftHeight - rightHeight) > 1) {return false;}// 更新当前节点高度（用于父节点计算）currentHeight = Math.max(leftHeight, rightHeight) + 1;// 若栈非空，更新父节点的高度（此处需更复杂的栈结构，实际中可用哈希表记录节点高度）prev = root;root = null; // 标记当前节点处理完毕}}return true;}// 辅助方法：从栈中获取已处理节点的高度（实际中更适合用哈希表记录）private int getStoredHeight(Stack<TreeNode> stack, Stack<Integer> heightStack, TreeNode node) {// 简化实现，实际需遍历栈或用哈希表，此处仅为示意return 0;}
}
实现难点
- 高度记录：递归中高度随递归栈自动传递，迭代中需显式用栈或哈希表记录每个节点的高度。
- 后序遍历顺序保证：通过标记
prev节点，确保左右子树处理完毕后再处理当前节点。 - 复杂度权衡：迭代法代码复杂度高，实际中常用哈希表存储节点高度，空间复杂度O(n)。
六、总结：递归与迭代的选择策略
回溯法（递归）的核心价值
- 代码简洁性：用最少的代码实现逻辑，适合快速验证算法正确性。
- 思维直观性：天然匹配树的递归结构，易于理解和调试。
迭代法的工程价值
- 稳定性：避免递归栈溢出，适合生产环境大规模数据。
- 面试加分项：体现对数据结构（栈）的灵活运用能力。
大厂面试建议
- 优先给出递归解法：确保逻辑正确，阐述剪枝优化思路。
- 主动补充迭代法：说明递归的潜在问题（栈溢出），并简要描述迭代思路（如后序遍历模拟）。
- 强调场景适配：小数据用递归，大数据用迭代，结合具体需求选择方案。
七、扩展思考：平衡树的其他变种
- AVL树：动态平衡二叉树，插入/删除时通过旋转保持平衡，本题为其平衡性判定的基础。
- 红黑树：弱平衡树，本题解法可作为其平衡性验证的参考。
理解平衡二叉树的判定逻辑，是掌握高级数据结构的重要基础。无论是递归还是迭代，核心都是通过有序遍历和条件剪枝，高效验证每个节点的平衡性。