计算机培训机构排名最新_智慧团建网站怎么转团关系_推广普通话宣传周_官网优化哪家专业

判断平衡二叉树的详解（Java 实现）

平衡二叉树的定义：
平衡二叉树（Balanced Binary Tree）是指一棵二叉树中任意节点的左右子树高度差不超过 1。即：
$$|height(left)-height(right)|\le 1$$
且其左右子树也是平衡二叉树。

---

实现步骤

1. 高度计算：通过递归方式计算每个节点的高度。
2. 平衡性判断：递归判断每个节点是否满足高度差小于等于 1 的条件。

---

方法 1：自顶向下递归（不优化）

1. 计算节点高度：从底部开始递归求节点高度。
2. 判断平衡性：对每个节点，检查左右子树的高度差是否满足条件。

代码实现：

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}
}public class BalancedBinaryTree {// 判断是否为平衡二叉树public boolean isBalanced(TreeNode root) {if (root == null) return true; // 空树是平衡的// 判断左右子树的高度差是否满足条件，并递归检查子树return Math.abs(height(root.left) - height(root.right)) <= 1&& isBalanced(root.left)&& isBalanced(root.right);}// 计算树的高度private int height(TreeNode node) {if (node == null) return 0; // 空节点高度为 0return Math.max(height(node.left), height(node.right)) + 1;}
}

分析：

• 时间复杂度： 每个节点调用一次 height，height 递归访问所有子节点，因此时间复杂度为 $O(n^2)$。
• 空间复杂度： 递归栈空间取决于树的高度，最差情况下为 $O(n)$（链式树）。

---

方法 2：自底向上递归（优化版）

改进思路：

• 在一次递归中同时计算高度和判断平衡性。
• 如果某个子树不平衡，直接返回，避免重复计算。

代码实现：

public class BalancedBinaryTree {// 判断是否为平衡二叉树public boolean isBalanced(TreeNode root) {return checkHeight(root) != -1; // 如果返回 -1，表示不平衡}// 递归检查平衡性，同时返回高度private int checkHeight(TreeNode node) {if (node == null) return 0; // 空节点高度为 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;// 返回当前节点的高度return Math.max(leftHeight, rightHeight) + 1;}
}

分析：

• 时间复杂度： 每个节点只访问一次，时间复杂度为 $O(n)$。
• 空间复杂度： 递归栈空间取决于树的高度，最差情况下为 $O(n)$（链式树）。

---

测试代码

public class Main {public static void main(String[] args) {// 构造一个平衡二叉树TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(2);root.left.left = new TreeNode(3);root.left.right = new TreeNode(3);root.left.left.left = new TreeNode(4);root.left.left.right = new TreeNode(4);BalancedBinaryTree tree = new BalancedBinaryTree();System.out.println(tree.isBalanced(root)); // 输出 false（该树不平衡）}
}

---

总结

1. 方法 1：自顶向下递归
   • 简单易懂，适用于小型树。
   • 时间复杂度较高，为 $O(n^2)$。
2. 方法 2：自底向上递归
   • 高效，适用于大型树。
   • 时间复杂度为 $O(n)$。

选择方法 2 是更优的方案，尤其是在树较大的情况下。