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

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