/**
 * @author wuze
 * @desc ...
 * @date 2021-05-06 00:07:23
 */
public class 平衡二叉树_判断是否高度平衡 {

    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 {

        /*
        思路：
        左右子树递归，判断层数
        自底向上！（时间复杂度 O(n) ）
        */
        boolean res=true;


        public boolean isBalanced(TreeNode root) {

            if(root==null){
                return true;
            }

            dfs(root);

            return res;
        }



        int dfs(TreeNode node){

            if(node==null){
                return 0;
            }

            int leftcount = dfs(node.left)+1;
            int rightcount = dfs(node.right)+1;

            if(Math.abs(rightcount-leftcount)>1){
                res=false;
            }

            //这个 return 是有讲究的！
            //（关键！）注意：每一次递归到的子树，都有左右子树，返回深度最大的！（左子树 or 右子树）！！！
            return Math.max(rightcount,leftcount);
        }
    }
}