java判断一颗二叉树是否是平衡二叉树

客官°小女子只卖身不卖艺 2024-03-16 10:52 44阅读 0赞

## 判断一颗二叉树是否是平衡二叉树 ##

### 题目描述 ###

一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

### 示例 ###

![在这里插入图片描述][e33fc6fc225a423cafb432868132cfe3.png]  
![在这里插入图片描述][5ba6bf8add6b4379a825d3d72757b365.png]

![在这里插入图片描述][11a578b5209f48bf898262e323012218.png]

### 原题OJ链接 ###

https://leetcode.cn/problems/balanced-binary-tree/

### 解答代码 ###

/**
     * 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;
     *     }
     * }
     */
     import java.lang.Math;
    class Solution {
        
        public boolean isBalanced(TreeNode root) {
        
            if(root == null){
        
                return true;
            }
            int leftH = getHeight(root.left);
            int rightH = getHeight(root.right);
            if((Math.abs(leftH-rightH)<=1) && isBalanced(root.left) && isBalanced(root.right)){
        
                return true;
            }
            return false;
    
    
        }
        public int getHeight(TreeNode root){
        //求树的深度（高度）
            if(root == null){
        
                return 0;
            }
            if(root.right == null && root.left == null){
        
                return 1;
            }
    //        int count1 = getHeight(root.left)+1;
    //        int count2 = getHeight(root.right)+1;
    //        return Math.max(count1,count2);
            return Math.max(getHeight(root.left)+1, getHeight(root.right)+1);
        }
    }

这段代码有一个缺点在于实际做了很多重复的工作，实际是在进行双层递归，每个结点都求了其左右子树的高度，不满足之差绝对值小于等于1才会返回false，但是实际上这个工作可以直接放在求高度的时候完成，左右子树高度之差的绝对值大于1就直接返回-1，后面结点的高度根本不需要求了，因为这表明这个树一定是不平衡的了。  
所以有如下代码

/**
     * 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;
     *     }
     * }
     */
     import java.lang.Math;
    class Solution {
        
        public boolean isBalanced(TreeNode root) {
        
            return maxDepth(root)>=0;
        }
        public int maxDepth(TreeNode root){
        
            if(root == null){
        
                return 0;
            }
           int count1 = maxDepth(root.left);
           if(count1<0){
        
               return-1;
           } 
           int count2 = maxDepth(root.right);
           if(count2<0){
        
               return -1;
           }
           if(Math.abs(count1-count2)<=1){
        
               return Math.max(count1,count2)+1;
           }
           else{
        
               return -1;
           }
        }
    }

[e33fc6fc225a423cafb432868132cfe3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/3c6a86798c044484b1eebf36542f7159.png
[5ba6bf8add6b4379a825d3d72757b365.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/b244aba12c174e15a49111358388a049.png
[11a578b5209f48bf898262e323012218.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/17fd5edc85d84a01b2011cc9b96c6633.png