平衡二叉树
最新回答
想念总是在夜里狂奔
2026-03-05 13:27:18
平衡二叉树的判断方法及优化
平衡二叉树是指每个节点的左右子树高度差不超过1的二叉树。以下是判断平衡二叉树的两种方法及其分析：
解法1：自顶向下递归（时间复杂度O(n2)）- 计算节点高度：对每个节点，递归计算其左右子树的高度。
- 判断平衡性：检查当前节点的左右子树高度差是否超过1，若超过则返回false；否则递归检查左右子树。
缺点：重复计算子树高度，导致效率低下。例如，计算根节点高度时会遍历整棵树，而计算其子节点高度时又会重复遍历部分子树。
解法2：自底向上递归（时间复杂度O(n)）- 优化思路：从叶子节点开始计算高度，并在递归返回时传递高度信息，避免重复计算。
- 提前终止：若发现任一子树不平衡，立即终止递归并返回false。
代码实现：
public class Solution { public boolean isBalanced(TreeNode root) { return checkHeight(root) != -1; } private int checkHeight(TreeNode node) { if (node == null) return 0; int leftHeight = checkHeight(node.left); if (leftHeight == -1) return -1; // 左子树不平衡 int rightHeight = checkHeight(node.right); if (rightHeight == -1) return -1; // 右子树不雹升烂平衡 if (Math.abs(leftHeight - rightHeight) > 1) { return -1; // 当前节点不平衡 } else { return Math.max(leftHeight, rightHeight) + 1; // 返回笑明当前节点高度 } }}关键点说明- 高度计算与平衡检查合并：在递归返回高度的同时检查平衡性，若子树不平衡则直接返回-1作为标记。
- 效率提升：每个节点仅被访问一次源漏，时间复杂度优化至O(n)。
- 终止条件：一旦发现不平衡子树，立即终止后续计算。
示例1（平衡树）：
3 / 9 20 / 15 7所有节点的左右子树高度差均≤1，返回true。
示例2（非平衡树）：
1 / 2 2 / 3 3 / 4 4节点2的左右子树高度差为2（左子树高度3，右子树高度0），返回false。
自底向上的方法通过一次遍历完成高度计算和平衡性检查，显著提升了效率，是判断平衡二叉树的最优解。
热门标签
