剑指offer-39、平衡⼆叉树
<h2 id="题描述">题⽬描述</h2><p>输⼊⼀棵节点数为 n ⼆叉树，判断该⼆叉树是否是平衡⼆叉树。</p>
<p>在这⾥，我们只需要考虑其平衡性，不需要考虑其是不是排序⼆叉树</p>
<p>平衡⼆叉树（ Balanced Binary Tree ），具有以下性质：它是⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不超过 1 ，并且左右两个⼦树都是⼀棵平衡⼆叉树。</p>
<p>样例解释：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202505251056341.png" alt="" loading="lazy"></p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="自顶向下递归基础解法">自顶向下递归（基础解法）</h3>
<p>平衡树意味着我们需要对⽐任何在同⼀个根下的左右⼦树的⾼度差，还记得之前我们计算树的⾼度么，使⽤递归⽅式来解决，其实这道题与算⾼度差不多，只是两边⾼度需要算出⼀个差值。</p>
<p>算法的主要思想：</p>
<ul>
<li>不断对⽐每两个节点的左右⼦树的最⼤⾼度差，注意取差的绝对值，需要⼩于等于1</li>
<li>对⽐完左右⼦树之后，需要递归左⼦树以及右⼦树进⾏分别判断，都满⾜才是平衡树</li>
</ul>
<pre><code class="language-java">public class Solution79 {
public boolean IsBalanced_Solution(TreeNode root) {
if (root == null) return true;
// 当前左右⼦树是否平衡以及左右⼦树分别是否平衡
return Math.abs(depth(root.left) - depth(root.right)) <= 1 &&
IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
private int depth(TreeNode root) {
if (root == null) {
return 0;
}
// 递归获取深度
return Math.max(depth(root.left), depth(root.right)) + 1;
}
}
</code></pre>
<ul>
<li>时间复杂度 O(nlogn) ：最差情况下，需要遍历树所有节点判断是否平衡，需要O(n)。但是判断每个节点最⼤⾼度需要递归左右⼦树，需要占⽤ O(log2n) ，所以总共占⽤ O(Nlog2n)</li>
<li>空间复杂度 O(n) ：最差情况下，也就是树退化为链表时，递归需要使⽤ O(n) 的栈空间，严格意义上递归栈也需要空间。</li>
</ul>
<h3 id="自底向上递归优化解法">自底向上递归（优化解法）</h3>
<p>上⾯的计算，仔细观察就会发现会有很多重复计算的过程，⽐如下⾯的数，计算⼦树深度的时候，计算 1 的左⼦树，和计算 2 的，基本都重复了。</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202505251131851.png" alt="" loading="lazy"></p>
<p>应该如何避免这种重复计算呢？前⾯的是⾃顶向下的⽅式，因为每个节点都得把⼦树计算⼀遍才需要重复，如果我们从下往上计算，那不就避免了重复计算。后序遍历，先判断子树平衡性，再判断当前节点，对⽐逻辑如下：</p>
<ul>
<li>如果当前节点为空，⾼度为0</li>
<li>如果当前节点的左⼦树的⾼度为-1，那么说明不平衡，否则，需要计算右⼦树⾼度，同样需要不等于-1，如果两者的差不符合⼩于等于1，那么说明它们不平衡，返回-1。通过这样 -1 异常值就会⼀路返回，到最初的调⽤处，得到不平衡的结果。</li>
</ul>
<pre><code class="language-java">public class Solution79 {
public boolean IsBalanced_Solution(TreeNode root) {
// 空树
if (root == null) {
return true;
}
return getHeight(root) != -1;
}
public int getHeight(TreeNode root) {
if (root == null) {
return 0;//空节点高度为0
}
// 左⼦树的⾼度
int left = getHeight(root.left);
if (left < 0) {
return -1;//左子树不平衡，直接返回
}
// 右⼦树的⾼度
int right = getHeight(root.right);
if (right < 0) {
return -1;//右子树不平衡，直接返回
}
// 检查当前节点是否平衡
return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}
}
</code></pre>
<ul>
<li>时间复杂度 O(n) ：每个节点计算⼀次</li>
<li>空间复杂度 O(n) ：递归需要使⽤额外堆栈空间</li>
</ul>
<p>笔试面试时，建议首选这个方式，效率最优，代码简洁</p>
<h3 id="封装信息法面向对象思路">封装信息法（面向对象思路）</h3>
<p>通过自定义类同时返回高度和平衡信息，代码结构更清晰。</p>
<pre><code class="language-java">class BalanceInfo {
boolean isBalanced;
int height;
BalanceInfo(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
}
public class Solution {
public boolean isBalanced(TreeNode root) {
return checkBalance(root).isBalanced;
}
private BalanceInfo checkBalance(TreeNode node) {
if (node == null) {
return new BalanceInfo(true, 0); // 空节点平衡且高度为0
}
// 递归检查左右子树
BalanceInfo leftInfo = checkBalance(node.left);
BalanceInfo rightInfo = checkBalance(node.right);
// 如果子树不平衡，直接返回
if (!leftInfo.isBalanced || !rightInfo.isBalanced) {
return new BalanceInfo(false, -1); // 高度值此时不重要
}
// 检查当前节点是否平衡
if (Math.abs(leftInfo.height - rightInfo.height) > 1) {
return new BalanceInfo(false, -1);
}
// 返回当前节点的平衡信息和高高度
int currentHeight = Math.max(leftInfo.height, rightInfo.height) + 1;
return new BalanceInfo(true, currentHeight);
}
}
</code></pre>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19226244
頁:
[1]