判断是不是平衡二叉树

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        returnType res = judge(pRoot);
        return res.isBS;
    }

    public returnType judge(TreeNode pRoot){
        //向左右子树索要信息：1. 左右子树的高度；2. 左右子树是否平衡
        returnType res = new returnType(0, false);
        if(pRoot == null){
            res.isBS = true;
            return res;
        }
        returnType l_res =  judge(pRoot.left);
        returnType r_res =  judge(pRoot.right);
        res.depth = Math.max(l_res.depth, r_res.depth) + 1;
        if(!l_res.isBS || !r_res.isBS) return res;
        if(Math.abs(l_res.depth - r_res.depth) > 1) return res;
        res.isBS = true;
        return res;
    }

    public class returnType {
        int depth = 0;
        boolean isBS = false;
        public returnType(int depth, boolean isBS){
            this.depth = depth;
            this.isBS = isBS;
        }
    } 
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        // write code here
        if (pRoot == null) {
            return true;
        } else  {
            if (Math.abs(maxDeep(pRoot.left) - maxDeep(pRoot.right)) <=1) {
                return true;
            } else return false;
        }
    }

    public int maxDeep(TreeNode root) {
        if (root != null ) {
            return 1 + Math.max(maxDeep(root.left), maxDeep(root.right));
        } else {
            return 0;
        }
    }
}

public class Solution {
    /**
     * 输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
     *
     *
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        if (null == pRoot) {
            return true;
        }
        if (Math.abs(getHeight(pRoot.left) - getHeight(pRoot.right)) > 1) {
            return false;
        }
        return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
    }

    public int getHeight(TreeNode pRoot) {
        if (null == pRoot) {
            return 0;
        }
        return 1 + Math.max(getHeight(pRoot.left), getHeight(pRoot.right));
    }

}

public boolean IsBalanced_Solution (TreeNode pRoot) {
        if(pRoot==null) return true;
        int ans=build(pRoot);
        if(ans>=1) return true;
        else return false;
    }
    public int build(TreeNode pRoot){  //返回树的高度
        if(pRoot==null){
            return 1;
        }
        int leftH=build(pRoot.left);
        int rightH=build(pRoot.right);
        if(Math.abs(leftH-rightH)>1){
            return -1;
        }
        return Math.max(leftH,rightH)+1;
    }

public class Solution {
    boolean res = true;
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null ) return true;
        panduan(root);
        return res;
    }

    public int panduan(TreeNode root){
        if(root == null) return 0;
        int left = 1+panduan(root.left);
        int right = 1+panduan(root.right);
        if(Math.abs(left - right) > 1){
            res=false;
        }
        return Math.max(left,right);
    }
}

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(getMaxDepth(root.left) - getMaxDepth(root.right)) > 1) {
            return false;
        }
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);

    }

    private int getMaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Integer.max(getMaxDepth(root.left), getMaxDepth(root.right)) + 1;
    }
}

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        boolean flag;
        if (root == null) return true;
        if (Math.abs(Maxdepth(root.left) - Maxdepth(root.right)) <= 1) {
            flag = true;
        } else {flag = false;}
        flag = flag && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
        return flag;
    }

    int Maxdepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(Maxdepth(root.left), Maxdepth(root.right)) + 1;
    }
}

public class Solution {
    boolean tag = true;
    public boolean IsBalanced_Solution(TreeNode root) {
        height(root);
        return tag;
    }

    private int height(TreeNode t) {
        if (t == null) return 0;

        int left = height(t.left);
        int right = height(t.right);

        if (Math.abs(left - right) > 1) tag = false;

        return left > right ? left + 1 : right + 1;
    }
}

import java.util.*;
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        //maybe递归---//是左右的高度差即深度差不大于1
        if(root==null){return true;}
        ArrayList<ArrayList<Integer>> list1=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> sublist1=new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> list2=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> sublist2=new ArrayList<Integer>();
        int level_left=level(root.left,list1,sublist1);
        int level_right=level(root.right,list2,sublist2);
        if(Math.abs(level_left-level_right)>1){return false;}
        return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
    
       
    }
    public int level(TreeNode root,ArrayList<ArrayList<Integer>> list,ArrayList<Integer> sublist){
        //用层序遍历来找深度try
        if(root==null){return 0;}
        Deque<TreeNode> deque=new LinkedList<TreeNode>();
        deque.addLast(root);
        int level=0;
        while(!deque.isEmpty()){
            for(int i=0;i<deque.size();i++){
                 TreeNode cur=deque.removeFirst();
                 sublist.add(cur.val);
                 if(cur.left!=null){deque.addLast(cur.left);}
                 if(cur.right!=null){deque.addLast(cur.right);}
            }
            list.add(new ArrayList(sublist));
            level=level+1;    
        }
        return level;    
    }
}

1. 左子树 和 右子树的深度不能超过 1；
2. 左子树 和 右子树 也是平衡二叉树；

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 按照平衡二叉树 递归定义：
        // 1. 左子树 和 右子树的深度不能超过 1；
        // 2. 左子树 和 右子树 也是平衡二叉树；
        return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    
    private int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

public class Solution {
    private boolean isBalanced = true;
    public boolean IsBalanced_Solution(TreeNode root) {
        getDepth(root);
        return isBalanced;
    }
    private int getDepth(TreeNode root){
        if(root == null) return 0;
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        
        if(Math.abs(left-right) > 1){
            isBalanced = false;
        }
        return Math.max(left,right)+1;
     }
}