【LeetCode刷题日记】一篇带你搞懂平衡二叉树高效判断法（110.平衡二叉树）

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰今天参加了学校的运动会然后晚上还参加了一个三个小时的急救知识培训所以今天的文章发的有点迟了我们今天继续刷二叉树相关的题。ps关于急救的知识大家还是要了解的生命第一要少熬夜希望大家都健健康康【摘要】本文介绍了判断平衡二叉树的两种方法。平衡二叉树的定义要求每个节点的左右子树高度差不超过1且左右子树也必须是平衡的。第一种自顶向下方法通过递归计算高度并判断平衡性但存在重复计算问题时间复杂度为O(n²)。推荐采用自底向上的后序遍历方法在计算高度的同时判断平衡性利用-1标记不平衡情况时间复杂度优化为O(n)。文章通过示例详细说明了后序遍历的执行过程并提供了完整的Java代码实现。题目背景110.平衡二叉树给定一个二叉树判断它是否是 平衡二叉树示例 1输入root [3,9,20,null,null,15,7]输出true示例 2输入root [1,2,2,3,3,null,null,4,4]输出false示例 3输入root []输出true提示树中的节点数在范围[0, 5000]内-104 Node.val 104题目解析首先我们要知道什么是平衡二叉树 根据题目说的平衡二叉树的定义每个节点的左右两个子树的高度差的绝对值不超过 1并且左右子树也分别是平衡二叉树为什么要左右子树也分别平衡我们看一个例子text1 / \ 2 3 / \ 4 5 / \ 6 7检查根节点1左子树高度 32→4→6右子树高度 33→5→7差值 0 ≤ 1 根节点平衡但是检查左子树节点2左子树高度 24→6右子树高度 0null差值 2 1 左子树不平衡所以整棵树不平衡核心思想平衡二叉树的定义是递归的一棵树是平衡的 ⇔ 左子树平衡 右子树平衡 |左高 - 右高| ≤ 1因此我们需要同时获取两个信息当前树的高度当前树是否平衡方案思路时间复杂度空间复杂度推荐自顶向下暴力先算高度再递归判断O(n²)O(n)❌自底向上推荐后序遍历边计算高度边判断O(n)O(n)✅方案一自顶向下暴力法不推荐java class Solution { public boolean isBalanced(TreeNode root) { if (root null) return true; // 判断当前节点是否平衡 int leftHeight getHeight(root.left); int rightHeight getHeight(root.right); if (Math.abs(leftHeight - rightHeight) 1) { return false; } // 递归判断左右子树 return isBalanced(root.left) isBalanced(root.right); } // 计算树的高度 private int getHeight(TreeNode root) { if (root null) return 0; return 1 Math.max(getHeight(root.left), getHeight(root.right)); } }问题getHeight()会被重复调用每个节点被访问多次时间复杂度 O(n²)。二、方案二自底向上推荐 核心思想后序遍历左右根先递归计算左子树的高度和平衡性再递归计算右子树的高度和平衡性如果左右子树都平衡且高度差 ≤ 1则当前树平衡返回当前树的高度给上一层使用巧妙之处用特殊值如 -1表示不平衡正常情况返回高度代码实现java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public boolean isBalanced(TreeNode root) { return getHeight(root) ! -1; } // 返回树的高度如果不平衡则返回 -1 private int getHeight(TreeNode root) { if (root null) { return 0; } // 递归计算左子树高度 int leftHeight getHeight(root.left); if (leftHeight -1) { return -1; // 左子树不平衡直接返回 -1 } // 递归计算右子树高度 int rightHeight getHeight(root.right); if (rightHeight -1) { return -1; // 右子树不平衡直接返回 -1 } // 检查当前节点是否平衡 if (Math.abs(leftHeight - rightHeight) 1) { return -1; // 当前节点不平衡 } // 返回当前树的高度 return 1 Math.max(leftHeight, rightHeight); } }关于return getHeight(root) ! -1的完整展开。java public boolean isBalanced(TreeNode root) { int heightOrFlag getHeight(root); // 得到 -1 或高度 if (heightOrFlag -1) { return false; // 不平衡 } else { return true; // 平衡 } }为什么每次都返回-11 / \ 2 3 / \ 4 5 / 6节点6正常 → 返回 1节点4左高1右高0差值1 → 返回 2节点5正常 → 返回 1节点2左高2右高1差值1 → 返回 3节点3正常 → 返回 1节点1左高3右高1差值2 → 返回-1一旦节点1返回 -1整个递归结束isBalanced收到 -1 →falsereturn 1 Math.max(leftHeight, rightHeight);这行代码返回的是树的高度一个正常值0,1,2,3...然后在外层的isBalanced中javapublic boolean isBalanced(TreeNode root) { return getHeight(root) ! -1; }如果getHeight(root)返回的是正常高度0,1,2...→! -1是true→ 平衡如果getHeight(root)返回的是-1→! -1是false→ 不平衡执行过程图解以平衡树为例text3 / \ 9 20 / \ 15 7后序遍历的顺序是硬性规定text对任意一棵树 1. 后序遍历左子树 2. 后序遍历右子树 3. 访问根节点不是“先左再根再右”也不是“哪边节点少先处理哪边”。具体套到这棵树上树结构3/ \9 20/ \15 7第 1 步从根节点 3 开始规则先去左子树9再去右子树20最后访问 3第 2 步进入左子树 9左空右空访问 9此时输出9第 3 步回到 3进入右子树 20规则对 20 这棵树先去左子树15再去右子树7最后访问 20第 4 步进入 15左右空访问 15此时输出9、15第 5 步回到 20进入右子树 7左右空访问 7此时输出9、15、7第 6 步回到 20左15已处理右7已处理访问 20此时输出9、15、7、20第 7 步回到 3左9已处理右20已处理访问 3最终输出9、15、7、20、3后序遍历过程步骤节点left高度right高度是否平衡返回高度1900✅121500✅13700✅142011✅25312✅3最终没有返回 -1 → 平衡