《二叉树刷题计划》——平衡二叉树

太过爱你忘了你带给我的痛 2024-04-23 15:39 102阅读 0赞

> ✅作者简介：大家好，我是小鱼儿，大家可以叫我鱼儿
> 
> ?博客首页：[是小鱼儿哈][Link 1]
> 
> ?系列专栏：[一起刷好题][Link 2]
> 
> ?每日一句**：勤奋这把可能变成现实，懒惰者把甜作苦受**
> 
> ?博主也在学习阶段，如发现问题请告知，非常感谢?

**再解答平衡二叉树这个问题前，我们先来看这样一个题目**

![88478be1e30e4701a99248247f707fe8.png][]

> ?这个问题我们可以转换为子问题求解，**如果我们知道了该二叉树的左子树和右子树的最大深度就相当于知道了该二叉树的深度**，同样**左子树和右子树也有各自他们所对应的左子树和右子树，这样我们还需要求他们各自的左右子树的深度，这就是一个从上到下的递归过程。**

> 把一个大规模的问题，拆分为多个小规模的子问题  
> ?要求3为根节点的二叉树深度：  
> ?以9为根节点的二叉树的深度x  
> ?以20为根节点的二叉树的深度y  
> 答案=**Max(9为根节点的二叉树的深度x,20为根节点的二叉树的深度y)+1**

![6a78cb84922f4447970eec2913d6797b.png][]

>     public int maxDepth(TreeNode root) {
>             if (root == null) return 0; // 递归结束的条件，root节点为null,深度自然为0
>             int leftHeight = maxDepth(root.left); // 求左子树的高度
>             int rightHeight = maxDepth(root.right);  // 求右子树的高度
>             //单层逻辑
>             //左子树的深度和右子树的深度最大的值+1就是二叉树的深度
>             return Math.max(leftHeight, rightHeight) + 1;
>         }

有了上面的基础，我们回过头来看我们的平衡二叉树问题

![5b0fcca97fe04b49b3e273cf3bb1f7a4.png][]

**分析：**

二叉树的每个节点的左右子树的高度差的绝对值不超过 1，则二叉树是平衡二叉树。高度差的绝对值不超过1好办（我们上面那个题不就是求高度的吗？）但问题是怎样确保每个结点的左右子树高度差都不超过1呢？

我们不妨换一种思路，如果一个树是平衡二叉树，**那么他的左子树和右子树也都必须是平衡二叉树才行。然后如果左子树想是一个平衡二叉树，那么该左子树他的左右子树是不是也必须是平衡二叉树呀！**

这样从上往下递归下去，**在递归的过程中我们一定是通过求当前结点的左右子树的高度来进行是否是平衡树的判断的，**那么在递归过程中我们其实就完成了对**每个结点左右子树高度的判断。**

>     class Solution {
>         // 求当前结点高度的函数
>         public int maxDepth(TreeNode root) {
>             if (root == null) return 0;
>             int leftHeight = maxDepth(root.left);
>             int rightHeight = maxDepth(root.right);
>             return Math.max(leftHeight, rightHeight) + 1;
>         }
>         // 一个树既然是平衡二叉树，那么他的所有子树都是平衡二叉树
>         public boolean isBalanced(TreeNode root) {
>             if (root == null) return true;
>             int left = maxDepth(root.left); // 递归求当前树左右子树的深度
>             int right = maxDepth(root.right);
>             if (left - right < -1 || left - right > 1) return false; // 如果差的绝对值大于一就返回false
>             return isBalanced(root.left) && isBalanced(root.right); 
>             // 递归判断每个节点是否是平衡二叉树,就该结点的左子树和右子树是否为平衡二叉树
>             // 只有当左子树和右子树都是平衡二叉树时，该树才是平衡二叉树
>         }
>     }

上面我们对每个结点其实都算了他的左右子树的高度，但很多情况下对每个结点都判断其实是没必要的，比如：

![4eaad9282de34566b37c732bee32977e.png][]

? 在这个二叉树中，很明显就不是一个平衡二叉树，比如结点9他的左子树的高度是2，右子树高度是0**，这明显就不符合题目中平衡二叉树的定义啊！那么我们能不能在求高度的时候，如果遇到高度差的绝对值大于1了，就直接说明该二叉树不平衡呢**？

> ?所以我们可以对于当前遍历到的节点，**先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平**衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），**否则返回 -1（仅仅只是把不平衡的子树标记起来，只要他与正常的高度返回值不同就行也可以是-100）。如果存在一棵子树不平衡，即返回了负数，则整个二叉树一定不平衡**。

>     class Solution {
>         // 求当前结点高度的函数
>         public int maxDepth(TreeNode root) {
>             if (root == null) return 0;
>             // 在求高度的过程中其实也进行了平衡二叉树的判断，
>             // 如果返回值为负数说明已经有一个子树不是平衡二叉树了，即整个树已经不是平衡二叉树了
>             int leftHeight = maxDepth(root.left);  // 所以接下来if里要加上leftHeight >= 0 && rightHeight >= 0这样的判断
>             int rightHeight = maxDepth(root.right);  // 如果为-1，已经不是正常情况，所以不能进入到接下来的if语句里
>             if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {
>                 return Math.max(leftHeight, rightHeight) + 1; // 正常情况下返回的一定大于0的
>             }
>             else {
>                 return -1;  // 说明该子树的不是平衡二叉树，即整个树就不是平衡二叉树
>             }
>         }
>         // 一个树既然是平衡二叉树，那么他的所有子树都是平衡二叉树
>         public boolean isBalanced(TreeNode root) {
>             return maxDepth(root)>=0; // 只有每个子树都是平衡二叉树，该数才是平衡二叉树
>             // 如果每个子树都是平衡的，累加的返回值不可能为负数（因为每个相加的高度都是整数）
>             // 如果一个子树返回了-1，及时其他的子树是正常的但因为我们再maxDepth的if语句里加了
>             // leftHeight >= 0 && rightHeight >= 0，所以正常的高度也不会返回，也不会把负数冲掉
>         }
>     }

再回顾一下就是：

*  一是我们需要先处理子树的深度再进行 比较
 *  二是如果我们在处理子树时发现其已经不平衡了，则可以返回一个-1，使得所有其长辈节 点可以避免多余的判断

[Link 1]: https://blog.csdn.net/weixin_61061381?type=blog
[Link 2]: https://blog.csdn.net/weixin_61061381/category_11776133.html
[88478be1e30e4701a99248247f707fe8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c9a529d522414bf0badcef9083429042.png
[6a78cb84922f4447970eec2913d6797b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/089270c47fe64af6bf6243789a2d4cc6.png
[5b0fcca97fe04b49b3e273cf3bb1f7a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/46713715b4c44d13b1f3751861d18759.png
[4eaad9282de34566b37c732bee32977e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/d7593c1f1ee3469b99054260d6579feb.png