110. 平衡二叉树（递归）

蔚落 2023-10-05 16:05 4阅读 0赞

#### 110. 平衡二叉树 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]

## 解题思路 ##

定义一个成员变量res，自顶向下遍历，在每次求出树的最大深度的过程中，要求左子树的最大深度和右子树的最大深度，每求出一个节点的左子树的最大深度和右子树的最大深度就把它们做个差。小于1满足条件不改变res。否则把res置为false，证明深度差超过了1.最后返回res就行

## 代码 ##

class Solution {
        
        boolean res=true;
        public boolean isBalanced(TreeNode root) {
        
           if(root==null){
        
               return true;
           }
           utils(root);
           return res;
        }
    
        public int utils(TreeNode root){
        //求树的最大深度
            if(root==null){
        
                return 0;
            }
            int left=utils( root.left);//左子树的深度
            int right=utils( root.right);//右子树的深度
            if(Math.abs(left-right)>1){
        //在求出每一个节点的左子树和右子树最大深度后，都进行一次减法运算，Math.bas()是把值转化为绝对值，避免出现负数干扰判断
                res= false;
            }
    
            return Math.max(left,right)+1;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201217233602191.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201217233611797.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70