力扣110.平衡二叉树-递归
📋 问题描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
平衡二叉树的定义：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
💡 解题思路
1. 理解平衡二叉树
平衡二叉树不仅仅是根节点的左右子树高度差不超过1，而是每个节点都必须满足这个条件。
关键点：
空树是平衡的
每个节点都需要检查
需要同时获取子树的高度和平衡状态
🔍 多种解法
解法1：自顶向下递归（朴素解法）
class Solution { public boolean isBalanced(TreeNode root) { if (root == null) return true; // 检查当前节点是否平衡 int leftHeight = height(root.left); int rightHeight = height(root.right); boolean currentBalanced = Math.abs(leftHeight - rightHeight) <= 1; // 递归检查左右子树 return currentBalanced && isBalanced(root.left) && isBalanced(root.right); } private int height(TreeNode root) { if (root == null) return 0; return Math.max(height(root.left), height(root.right)) + 1; } }复杂度分析：
时间复杂度：O(n²) - 每个节点都要计算高度，而高度计算本身也是O(n)
空间复杂度：O(n) - 递归栈深度
缺点：存在大量重复计算
解法2：自底向上递归（最优解）
class Solution { public boolean isBalanced(TreeNode root) { return dfs(root) != -1; } private int dfs(TreeNode node) { if (node == null) { return 0; } // 递归获取左子树高度 int h_left = dfs(node.left); if (h_left == -1) { return -1; } // 递归获取右子树高度 int h_right = dfs(node.right); if (h_right == -1) { return -1; } // 检查当前节点是否平衡 if (Math.abs(h_left - h_right) > 1) { return -1; } // 返回当前节点的高度 return Math.max(h_left, h_right) + 1; } }复杂度分析：
时间复杂度：O(n) - 每个节点只访问一次
空间复杂度：O(h) - 递归栈深度，h为树的高度
优点：
一次遍历同时完成高度计算和平衡判断
避免重复计算
尽早发现不平衡情况并终止递归
解法3：迭代法（避免递归栈溢出）
java
import java.util.*; class Solution { public boolean isBalanced(TreeNode root) { if (root == null) return true; Map<TreeNode, Integer> heights = new HashMap<>(); Deque<TreeNode> stack = new ArrayDeque<>(); // 后序遍历 TreeNode lastVisited = null; TreeNode node = root; while (!stack.isEmpty() || node != null) { if (node != null) { stack.push(node); node = node.left; } else { TreeNode peek = stack.peek(); if (peek.right != null && peek.right != lastVisited) { node = peek.right; } else { TreeNode curr = stack.pop(); int leftHeight = heights.getOrDefault(curr.left, 0); int rightHeight = heights.getOrDefault(curr.right, 0); if (Math.abs(leftHeight - rightHeight) > 1) { return false; } heights.put(curr, Math.max(leftHeight, rightHeight) + 1); lastVisited = curr; } } } return true; } }复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n)
适用场景：树非常深，递归可能导致栈溢出时使用
📊 算法对比表
| 方法 | 时间复杂度 | 空间复杂度 | 代码复杂度 | 适用场景 | 推荐指数 |
|---|---|---|---|---|---|
| 自顶向下递归 | O(n²) | O(n) | 简单 | 小规模数据 | ⭐⭐ |
| 自底向上递归 | O(n) | O(h) | 简单 | 通用场景 | ⭐⭐⭐⭐⭐ |
| 迭代法 | O(n) | O(n) | 中等 | 避免栈溢出 | ⭐⭐⭐ |
🎯 面试技巧
1. 问题分析步骤
text
1. 确认平衡二叉树的定义 2. 思考暴力解法（自顶向下） 3. 分析暴力解法的缺点（重复计算） 4. 优化思路（自底向上，一次遍历） 5. 实现优化解法
2. 代码实现要点
使用-1表示不平衡状态
尽早返回，减少不必要的递归
注意空树是平衡的特殊情况
3. 复杂度分析
时间：O(n) - 每个节点访问一次
空间：O(h) - 递归栈深度，最坏情况O(n)
4. 常见Follow-up问题
Q：如果树非常大，递归会栈溢出怎么办？
A：可以使用迭代版本，用栈模拟递归。Q：能写出非递归版本吗？
A：使用后序遍历的迭代实现，同时记录节点高度。Q：如何测试你的算法？
A：测试用例应包括：空树、单节点树、完全平衡树、完全不平衡树、随机树。
💡 实战练习
练习1：修改问题 - 返回不平衡的节点
java
public TreeNode findUnbalancedNode(TreeNode root) { // 修改dfs函数，返回不平衡节点 // 练习：实现这个函数 }练习2：计算树的最大深度差
java
public int maxHeightDifference(TreeNode root) { // 返回树中任意节点左右子树的最大高度差 // 练习：实现这个函数 }📝 总结
判断平衡二叉树是一个经典的二叉树问题，考察对递归、树遍历和算法优化的理解。自底向上递归解法是最优解，兼具效率高和代码简洁的优点。
关键收获：
平衡二叉树要求每个节点都满足平衡条件
自底向上的思路可以避免重复计算
使用特殊返回值（如-1）可以同时传递高度和状态信息
递归和迭代可以互相转换，各有适用场景
掌握这个问题不仅有助于解决LeetCode 110，还能加深对树相关算法的理解，为更复杂的树问题打下基础。
🔗 相关题目
104. 二叉树的最大深度
111. 二叉树的最小深度
543. 二叉树的直径