判断二叉树是否为平衡二叉树、求二叉树深度
最新回答
言清欢
2026-10-30 08:46:39
答案：要判断二叉树是否为平衡二叉树，需满足以下条件：
- 空树是平衡二叉树。
- 非空树的左右子树高度差绝对值不超过1。
- 左右子树本身也是平衡二叉树。
实现方法：通过递归计算左右子树的高度，并在过程中检查高度差。若发现不平衡，则标记并提前终止递归。
private boolean isBalanced = true;public boolean IsBalanced_Solution(TreeNode root) { balance(root); return isBalanced;}private int balance(TreeNode root) { if (root == null || !isBalanced) return 0; int left = balance(root.left); int right = balance(root.right); if (Math.abs(left - right) > 1) isBalanced = false; return 1 + Math.max(left, right);}关键点：
- 递归终止条件：节点为空时返回高度0。
- 高度计算：当前节点高度为 1 + max(左子树高度, 右子树高度)。
- 平衡性检查：若左右子树高度差超过1，标记 isBalanced = false。
答案：二叉树的深度（高度）是根节点到最远叶子节点的最长路径上的节点数。可通过递归计算左右子树深度并取最大值。
实现方法：递归遍历左右子树，返回较大深度值加1。
public int TreeDepth(TreeNode root) { return Deep(root);}private int Deep(TreeNode root) { if (root == null) return 0; int l = Deep(root.left); int r = Deep(root.right); return 1 + Math.max(l, r);}关键点：
- 递归终止条件：节点为空时返回深度0。
- 深度计算：当前节点深度为 1 + max(左子树深度, 右子树深度)。
平衡性判断优化：原代码在发现不平衡后仍继续递归计算高度，可通过返回特殊值（如-1）提前终止：
private int balance(TreeNode root) { if (root == null) return 0; int left = balance(root.left); if (left == -1) return -1; int right = balance(root.right); if (right == -1) return -1; return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);}深度计算简化：原代码中 l++ 和 r++ 是冗余的，直接在返回时加1即可。
时间复杂度：两种操作均为 O(n)，每个节点仅访问一次。
平衡二叉树示例：
3 / 9 20 / 15 7- 左右子树高度差为0，且子树均平衡，故为平衡二叉树。
非平衡二叉树示例：
1 / 2 2 / 3 3 / 4 4- 根节点左右子树高度差为1，但左子树高度差为2，整体不平衡。
- 平衡性判断：递归检查高度差并传递平衡状态。
- 深度计算：递归取左右子树最大深度加1。
- 优化方向：通过提前终止减少不必要的计算。
热门标签
