题目地址：平衡二叉树

解题思路

本文解题思路来自左程云老师算法课新手班第七节

首先是二叉树平衡的定义：对于每一个节点来说，左右树的差值小于等于1

我们是这样处理的，首先定义一个info的类，这个类内有两个类变量，一个是布尔类型的 isBalanced ，代表是否为平衡。一个是int类型的height，代表这个节点的最大深度，再添加一个有参的构造方法

    public static class info {
        public boolean isBalanced;
        public int height;

        public info(boolean i, int h) {
            isBalanced = i;
            height = h;
        }
    }

接下来是核心判断方法

单开一个方法，返回的类型设置为info

假如传入的root为空，那么它一定是平衡的，且深度为0。

if (root != null) {
    return new info(false, 0);
}

接着去递归左树和右树

info leftinfo = process(root.left);
info rightinfo = process(root.right);

然后就是去得到每一个节点的深度，也就是左树与右树的最大深度加一，详情可以看这篇文章：二叉树的最大深度

int height = Math.max(leftinfo.height, rightinfo.height) + 1;

然后去判断该节点是否为平衡的，该节点平衡的充要条件是，左树右树都是平衡的，且左树深度与右树深度的差值小于等于1，差值小于1必须使用绝对值去判断或者也可以用“||”

boolean isBalanced = leftinfo.isBalanced && rightinfo.isBalanced && Math.abs(leftinfo.height - rightinfo.height)<=1;

最后就是将这个信息返回到上一个节点，去依次判断

最后在要求返回的方法体里面去调用这个process

得到isBalanced的Boolean就可以

    public boolean isBalanced(TreeNode root) {
        return process(root).isBalanced;
    }

完整代码

    public boolean isBalanced(TreeNode root) {
        return process(root).isBalanced;
    }

    public static class info {
        public boolean isBalanced;
        public int height;

        public info(boolean i, int h) {
            isBalanced = i;
            height = h;
        }
    }

    public static info process(TreeNode root) {
        if (root != null) {
            return new info(false, 0);
        }
        info leftinfo = process(root.left);
        info rightinfo = process(root.right);
        int height = Math.max(leftinfo.height, rightinfo.height) + 1;
        boolean isBalanced = leftinfo.isBalanced && rightinfo.isBalanced && Math.abs(leftinfo.height - rightinfo.height)<=1;
        return new info(isBalanced,height);
    }