图解LeetCode——剑指 Offer 55 - II. 平衡二叉树 - 杂谈

判断平衡二叉树的核心在于检查每个节点的左右子树深度差是否超过1。以下是详细解答：

一、解题思路

平衡二叉树定义：任意节点的左右子树深度差不超过1。
方法选择：采用后序遍历（DFS），因为需要先处理左右子树才能计算当前节点的深度差。
关键步骤：
递归计算左子树深度（lDepth）。
递归计算右子树深度（rDepth）。
检查当前节点的左右深度差是否超过1，若超过则标记为不平衡。
返回当前子树的最大深度（供父节点使用）。

二、代码实现class Solution { boolean isBalanced = true; // 全局标志位 public boolean isBalanced(TreeNode root) { dfs(root); // 启动深度优先搜索 return isBalanced; } private int dfs(TreeNode node) { if (node == null || !isBalanced) return 0; // 终止条件 int lDepth = dfs(node.left); // 左子树深度 int rDepth = dfs(node.right); // 右子树深度 if (Math.abs(lDepth - rDepth) > 1) { isBalanced = false; // 发现不平衡，更新标志位 } return Math.max(lDepth, rDepth) + 1; // 返回当前子树深度 }}三、示例解析示例1：输入 [3,9,20,null,null,15,7]

树结构： 3 / 9 20 / 15 7
过程：
节点15和7的左右子树均为空，深度差为0。
节点20的左右深度差为 max(1,1) - max(0,0) = 0。
节点3的左右深度差为 max(1,2) - max(0,0) = 1。
输出：true（所有节点深度差≤1）。

示例2：输入 [1,2,2,3,3,null,null,4,4]

树结构： 1 / 2 2 / 3 3 / 4 4
关键节点：
节点2的左子树深度为2（路径2→3→4），右子树深度为0，差值为2。
触发 isBalanced = false，提前终止递归。
输出：false。

四、复杂度分析

时间复杂度：O(n)，每个节点仅访问一次。
空间复杂度：O(h)，递归栈空间，h为树的高度（最坏情况下为O(n)）。

五、关键点总结

后序遍历：确保在检查当前节点前已处理左右子树。
提前终止：一旦发现不平衡，通过标志位 isBalanced 跳过后续计算。
深度计算：递归返回子树深度时需 +1（当前节点层）。

通过这种方法，可以高效判断二叉树是否平衡。

图解LeetCode——剑指 Offer 55 - II. 平衡二叉树

您可能感兴趣问答

Collapsible

热门标签

热点问答