平衡二叉树

110.平衡二叉树

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

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

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

递归

用高度为-1表示以该结点的为根的树为不平很二叉树

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(get_depth(root)==-1){
            return false;
        }else{
            return true;
        }
    }
    
    //递归法
    public int get_depth(TreeNode root){
         if(root==null){
             return 0;
         }
         int left_depth = get_depth(root.left);
         int right_depth = get_depth(root.right);
         if(left_depth == -1 || right_depth == -1){  //左子树和右子树已经不平衡
             return -1;
         }
         if(Math.abs(left_depth-right_depth)>1){ //左右子树高度差>1，不平衡
             return -1;
         }else{  //否则返回该子树的高度
             return Math.max(left_depth,right_depth) + 1;
         }
    }
}