CS-Notes 剑指 Offer 55.2 详解平衡二叉树的判定与自底向上后序遍历解法【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本文基于 CS-Notes 仓库中 剑指 Offer 55.2 平衡二叉树题解 展开围绕“判断一棵二叉树是否为平衡二叉树”这一经典面试问题完整讲解平衡树的定义、自顶向下与自底向上两种解法的复杂度差异、原题 O(n) 解法的逐行实现与提前剪枝原理并串联仓库内的二叉树深度、Leetcode 110 等相关题解。读完后你可以独立推导树高类问题的最优递归写法理解全局标记变量加提前终止的设计意图并了解它在多线程场景下的替代方案。1. 题目描述与平衡二叉树的定义原题给出的定义只有一句话平衡二叉树左右子树高度差不超过 1。这句话的严谨含义是对树中的每一个节点其左子树高度与右子树高度之差的绝对值都不超过 1。满足该性质的二叉树也称为高度平衡二叉树AVL 树即在此基础上增加了插入删除时通过旋转维持平衡的操作。用文字画出 Leetcode 题解 - 树 中给出的判定示例3 / \ 9 20 / \ 15 7节点 9左右子树高度差 |0 - 0| 0平衡节点 20左右子树高度差 |1 - 1| 0平衡根节点 3左子树高度 1右子树高度 2高度差 |1 - 2| 1不超过 1整棵树平衡。如果把节点 15 换成一条更长的链例如 20 下方接 3 层节点右子树高度变成 4根节点高度差为 3判定结果即为 false。可见判定必须发生在每个节点上而不能只看根节点。2. 前置知识树的深度判断平衡的前提是求子树高度。仓库中 55.1 二叉树的深度 给出了标准后序递归写法public int TreeDepth(TreeNode root) { return root null ? 0 : 1 Math.max(TreeDepth(root.left), TreeDepth(root.right)); }它的结构就是后续 55.2 解法中height()函数的骨架空节点高度为 0否则高度等于左右子树高度的较大值加 1。55.2 实际上是在这个骨架里“顺路”检查了每个节点的高度差因此两道题应放在一起复习。3. 朴素解法自顶向下重复计算高度最直观的思路是对每个节点分别求左右子树深度再比较public boolean isBalanced(TreeNode root) { if (root null) return true; int leftDepth TreeDepth(root.left); int rightDepth TreeDepth(root.right); return Math.abs(leftDepth - rightDepth) 1 isBalanced(root.left) isBalanced(root.right); }正确但效率差TreeDepth在判断父节点时已经算过子树高度递归到子节点时又重新计算了一遍。对于 n 个节点的左斜链每个节点只有左孩子自顶向下方案需要 O(n) (n-1) (n-2) ... 次高度计算最坏时间复杂度为 O(n²)且即使发现最底层某节点已经失衡上层递归仍会照常遍历完整棵树无法提前结束。4. 原题解法自底向上后序遍历 全局标记原题解 采用的是后序遍历自底向上一次遍历同时完成“求高度”与“判平衡”两件事private boolean isBalanced true; public boolean IsBalanced_Solution(TreeNode root) { height(root); return isBalanced; } private int height(TreeNode root) { if (root null || !isBalanced) return 0; int left height(root.left); int right height(root.right); if (Math.abs(left - right) 1) isBalanced false; return 1 Math.max(left, right); }逐行拆解其设计代码作用private boolean isBalanced true;全局标记初始假定整棵树平衡遍历中一旦发现问题节点即置为 false。牛客/剑指 Offer 的判题器是单线程单例调用这种写法可以直接通过if (root null \|\| !isBalanced) return 0;两个终止条件一是空节点高度为 0二是一旦已确认失衡立即剪枝后续递归全部返回 0 快速退出避免无谓遍历int left height(root.left); int right height(root.right);先递归左右子树后序拿到子树真实高度if (Math.abs(left - right) 1) isBalanced false;当前节点失衡打上标记。注意此处不立即 return高度仍需正常返回供上层继续计算return 1 Math.max(left, right);当前子树高度 较高子树高度 1与 55.1 的TreeDepth完全同构复杂度分析时间复杂度 O(n)每个节点最多访问一次!isBalanced剪枝只会在失衡时让访问次数更少不会更多。空间复杂度 O(h)h 为树高是递归调用栈深度平衡树为 O(log n)最坏退化为链状时 O(n)。这里的关键思想是把“判断”寄生在“求高度”的回溯过程里。后序遍历保证了到达某个节点时其左右子树高度已经确定一次递归同时回答两个问题而自顶向下方案里高度需要被反复重算这正是两者复杂度差的根源。5. 改进写法避免全局变量原题用成员变量isBalanced传递结论简单直接但有两个工程隐患一是判题器之外多次调用同一实例时状态会残留第二次调用前需手动重置二是该对象若被多线程共享存在竞态。可以改为用返回值同时携带“高度与结论”——约定失衡时返回 -1public boolean isBalanced(TreeNode root) { return check(root) ! -1; } // 返回子树高度失衡时返回 -1 private int check(TreeNode root) { if (root null) return 0; int left check(root.left); if (left -1) return -1; // 左子树已失衡直接剪枝 int right check(root.right); if (right -1) return -1; if (Math.abs(left - right) 1) return -1; return 1 Math.max(left, right); }两种写法时间、空间复杂度相同后者无共享可变状态在面试白板之外的实际代码中更常用。6. 仓库内相关题解同属“树高/后序遍历”问题族的仓库文档建议按下面的顺序交叉复习55.1 二叉树的深度height()函数的原型先掌握“后序求高度”这一基本功Leetcode 题解 - 树其中“2. 平衡树”一节用maxDepth 全局result标记解决了 Leetcode 110 (Balanced Binary Tree)与本篇 55.2 是同一模式的两个版本对比阅读可以看到同一思路在两套题面上的映射树中两个节点的最低公共祖先普通二叉树版 LCA 同样是“后序遍历 子树结论合并”的结构其return left null ? right : right null ? left : root;一行合并左右子树结论的写法与本题合并左右子树高度的思想一致剑指 Offer 题解 - 目录完整的剑指 Offer 题解索引“树”分类下包含本篇及上述所有题目。7. 小结与面试要点定义要答全平衡二叉树要求每个节点的左右子树高度差都不超过 1只检查根节点是错误答案的典型来源首选自底向上后序遍历中顺便记录高度每个节点只访问一次O(n) 时间自顶向下重复求高度的写法最坏 O(n²)面试中可作为对比方案引出剪枝与状态传递原题通过!isBalanced提前终止递归确认失衡后不再深入无关节点用返回值-1 表示失衡代替全局布尔可以避免状态残留与线程安全问题同族问题树深度55.1、两节点最长路径、直径等题都复用“后序回溯返回高度”的骨架掌握本篇解法后可直接迁移。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考