力扣110 判断是否是平衡二叉树

力扣110 判断是否是平衡二叉树

题目：

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

• 树中的节点数在范围 [0, 5000] 内
• -104 <= Node.val <= 104

解题思路：

要判断一棵二叉树是否是一颗平衡二叉树我们就要判断这颗二叉树的每颗子树的高度差的绝对值要小于2，我们可以定义一个类Info这个类的信息包含它是否是平衡二叉树以及树的高度，递归的判断左子树与右子树然后再根据左子树与右子树的Info信息来判断这棵树是否是平衡二叉树。

代码：

/**
 * 判断一棵树是否是平衡二叉树
 * 平衡二叉树：每颗子树以及整颗树的左右子树的高度差不大于1
 */
public class IsBalancedTree {
    //1.首先定义一个二叉树的节点类型的类
    public static class TreeNode{
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    //2.再定义一个类这个类包括的信息是:是否是平衡二叉树以及这颗树的高度
    public static class Info{
        public boolean isBalancedTree;
        public int height;

        public Info(boolean isBalancedTree, int height) {
            this.isBalancedTree = isBalancedTree;
            this.height = height;
        }
    }

    //3.定义一个方法用来获取是否是平衡以及树的高度的信息
    public static Info process(TreeNode root){
        //4.1如果根节点为空那么默认为它就是一颗平衡二叉树
        if (root == null) {
            return new Info(true,0);
        }
        //4.2获得左子树的Info信息以及右子树的Info信息
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        //4.3获得整棵树的高度 左子树与右子树谁的高度高 高的再加1就是整棵树的高度
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        //4.4判断是否是平衡二叉树 要是平衡二叉树则左子树是平衡二叉树右子树也是平衡二叉树且左右子树的高度差的绝对值小于2
        boolean isBalanced = leftInfo.isBalancedTree && rightInfo.isBalancedTree
                && Math.abs(leftInfo.height - rightInfo.height) < 2;
        return new Info(isBalanced,height);
    }

    //4.定义一个方法判断是否是平衡的
    public static boolean isBalanced(TreeNode root){
        return process(root).isBalancedTree;
    }
}