// @Title: 平衡二叉树 (Balanced Binary Tree)
// @Author: qisiii
// @Date: 2022-03-01 17:27:53
// @Runtime: 1 ms
// @Memory: 40.5 MB
// @comment: 
// @flag: 
/**
 * 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;
 *     }
 * }
 */
class Solution {
   public boolean isBalanced (TreeNode root) {
    if(root==null){
        return true;
    }
    //计算当前子树的差&&左子树是平衡&&右子树是平衡
      boolean current=Math.abs(doHigh(root.left)-doHigh(root.right))<=1;
    return current&&isBalanced(root.left)&&isBalanced(root.right);
    }
    
    public int doHigh(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left!=null||root.right!=null){
            return Math.max(doHigh(root.left),doHigh(root.right))+1;
        }
        return 1;
    }
}

// @Title: 平衡二叉树 (Balanced Binary Tree)
// @Author: qisiii
// @Date: 2024-09-16 00:47:57
// @Runtime: 1 ms
// @Memory: 43.3 MB
// @comment: 
// @flag: 
/**
 * 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;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        if(Math.abs(depth(root.left)-depth(root.right))>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }
    public int depth(TreeNode root){
        if(root==null){
            return 0;
        }
        return Math.max(depth(root.left),depth(root.right))+1;
    }
}