算法打卡Day21_leetcode _110.平衡二叉树

这世上，有一条路不能选择，那就是放弃的路；有一条路不能拒绝，那就是成长的路。新时代要有新作为，每个人都是一种色彩，都是“不一样的烟火”。

——《做好人生的选择题》

Leetcode原题

110.平衡二叉树

思路

什么是平衡二叉树呢，就是它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。所以我们的思路只要分别计算出左右子树的高度，然后相减绝对值小于1就判为平衡二叉树，否则返回-1，不是平衡二叉树。

方法一 递归

class Solution {
   public boolean isBalanced(TreeNode root){
        if (root ==null){
            return true;
        }
       return helper(root)!= -1;
   }
   private int helper(TreeNode root){
        if (root==null){
            return 0;
        }

        int left_h =helper(root.left); //左子树高度
        int right_h =helper(root.right); //右子树高度
        if (left_h== -1 || right_h == -1 || Math.abs(left_h- right_h)>1){ //判断左右子树高度是否大于1，大于1说明不是平衡二叉树
            return -1;
        }
        return Math.max(left_h,right_h)+1;
   }
}

有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取 最新java面试资料以及简历模型120套哦~