题解 | #判断二叉树是否为平衡二叉树# DFS遍历树判断是否是平衡二叉树

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /*
         平衡二叉树：对于任何一个节点来说，他的左右子树高度差不能超过1；

         解题思路：直接DFS遍历每一节点，判断节点的左右子树的高度差。如果超过1，直接不是平衡二叉树。
    */
    public boolean isBalanced (TreeNode root) {
        if(root==null) return true;
        return dfs(root);
    }

    public boolean dfs(TreeNode root){
        // 获取当前节点的左子树高度
        int leftHeight = getHeight(root.left);
        // 获取当前节点的右子树高度 
        int rightHeight = getHeight(root.right);
        // 比较左右子树高度差
        if(Math.abs(leftHeight-rightHeight)>1) return false;

        // 假设左右子树都合法；
        boolean leftSign=true;
        boolean rightSign=true;
        // 递归左子树
        if(root.left!=null){
            leftSign = dfs(root.left);
        }
        // 递归右子树
        if(root.right!=null){
            rightSign = dfs(root.right);
        }

        // 只有当前节点的左右子树都合法，才说明当前节点合法
        if(leftSign && rightSign){
            return true;
        }else{
            return false;
        }
    }

    // 获取一个节点的高度
    public int getHeight(TreeNode root){
        if(root==null) return 0;
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }


    // 如果以上代码看得懂！判断平衡二叉树可以简化成这样写。 
  public boolean isBalanced (TreeNode root) {
        // 递归终止条件
         if(root==null) return true;
        
        // 如果当前节点高度差合法， 并且当前节点的左子树是合法 并且 当前节点的右子树是合法
       return Math.abs(getHeight(root.left)-getHeight(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right); }




}