题解 | #判断是不是平衡二叉树#

    
    // 定义一个内部类，用于封装每棵子树应该返回给原树
    class returnData {
        boolean isBalanced; // 子树是否是平衡二叉树
        int height; // 子树的高度是多少
        returnData(boolean isBalanced, int height) { // 构造函数
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }
    
    public boolean IsBalanced_Solution(TreeNode root) {
        if (null == root) {
            return true;
        }
        if (null == root.left && null == root.right) {
            return true;
        }
        // 调用递归函数
        returnData rs = IsBalanced(root);
        return rs.isBalanced;
    }
    
    // 判断一棵树是否是平衡二叉树的具体实现
    public returnData IsBalanced(TreeNode root) {
        if (null == root) {
            return new returnData(true, 0); // 如果空节点，那么这棵树是平衡二叉树，高度为 0
        }
        returnData leftData = IsBalanced(root.left); // 获取左子树的信息
        returnData rightData = IsBalanced(root.right); // 获取右子树的信息
        // 只有满足左右子树均是平衡二叉树，且左右子树的高度差小于 2 的情况下，这棵树才是平衡二叉树
        boolean isBalanced = leftData.isBalanced && rightData.isBalanced && Math.abs(leftData.height - rightData.height) < 2;
        return new returnData(isBalanced, Math.max(leftData.height, rightData.height) + 1); // 别忘了，当前树的高度是左右子树中高度最大的那棵树的高度 + 1！！！
    }
}