判断是不是平衡二叉树

public boolean IsBalanced_Solution (TreeNode pRoot) {
        if(pRoot == null) return true;
        int l = traserval(pRoot.left);
        int r = traserval(pRoot.right);

        return IsBalanced && Math.abs(l - r) <= 1;
    }
    boolean IsBalanced = true;
    public int traserval (TreeNode pRoot) {
        if(pRoot == null || !IsBalanced) return 0;
        int l = traserval(pRoot.left);
        int r = traserval(pRoot.right);
        if(Math.abs(l - r) >1) IsBalanced = false;
        return Math.max(l,r) + 1;
    }

public boolean IsBalanced_Solution (TreeNode pRoot) {
        // 自底向上找
        return recur(pRoot) != -1;
    }

    public int recur(TreeNode curnode){
        //空树也是平衡二叉树，及递归出口
        if(curnode == null) return 0;
        //求树的左边高度
        int lefthigh = recur(curnode.left);
        if(lefthigh == -1) return -1;
        //求树的右边高度
        int righthigh = recur(curnode.right);
        if(righthigh == -1) return -1;
        //判断左右高度差
        return Math.abs(lefthigh - righthigh) < 2 ? Math.max(lefthigh, righthigh) + 1 : -1;
    }

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        // write code here
        return dfs(pRoot) != -1;
    }
    public int dfs(TreeNode pRoot){
        if(pRoot == null) return 0;
        int left = dfs(pRoot.left);
        int right = dfs(pRoot.right);
        //左/右子树为非平衡二叉树
        if(Math.abs(left - right) > 1 || left == -1 || right == -1){
            return -1;
        }
        return Math.max(right, left) + 1;
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public class Info {
        public boolean isBalanced;
        public int maxDepth;

        public Info () {
            this.isBalanced = true;
            this.maxDepth = 0;
        }

        public Info (boolean isBalanced, int maxDepth) {
            this.isBalanced = isBalanced;
            this.maxDepth = maxDepth;
        }
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        // write code here

        // 1.我要干什么：
        //        获知【左子树】中【是否平衡，最大深度多少】
        //        获知【右子树】中【是否平衡，最大深度多少】

        // 2.我需要什么信息：
        //      综上所述，我需要左右子树的【是否平衡，最大深度多少】

        // 3.我如何利用两个子树的信息加工出来我的信息：
        //      若左右两个子树都平衡，且最大深度相差<=1，则本子树平衡

        // 调用递归函数求解
        return process(pRoot).isBalanced;
    }

    public Info process(TreeNode root) {
        // 递归出口
        if (root == null) {
            return new Info();
        }

        // 从左右子树获取信息
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);

        // 根据获取到的信息加工出自己的信息
        boolean isBalanced = leftInfo.isBalanced &&
                             rightInfo.isBalanced &&
                             (Math.abs(leftInfo.maxDepth - rightInfo.maxDepth) <= 1);
        int maxDepth = Math.max(leftInfo.maxDepth, rightInfo.maxDepth) + 1;
        return new Info(isBalanced, maxDepth);
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

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

    private int dfs(TreeNode pRooot) {
        if (pRooot == null) {
            return 0;
        }

        int left =  dfs(pRooot.left);
        int right = dfs(pRooot.right);

        if (Math.abs(left - right) > 1 || left == -1 || right == -1) {
            return -1;
        }

        return Math.max(left, right) + 1;
    }
}

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;
    }
}