package com.jiucaiyuan.algrithm.tree;

/**

 * 判断树是否为平衡二叉树

 * <p>

 * Created by jiucaiyuan on 2022/2/4.

 */

public class BalancedTreeSolution {



    //传递参数

    // 1. 传入根节点

    // 2. 返回是否为平衡二叉树

    public static boolean isBalanced(TreeNode root) {

        // 退出条件

        // 1. 节点为空，则为平衡二叉树

        if (null == root) {

            return true;

        }

        // 2. 左右节点不是平衡二叉树，则根节点不是平衡二叉树

        if (!isBalanced(root.left) || !isBalanced(root.right)) {

            return false;

        }

        // 单层逻辑

        // 1. 计算左节点深度

        // 2. 计算右节点深度

        // 3. 计算左右节点深度的差的绝对值是否>阈值1

        return Math.abs(deep(root.left) - deep(root.right)) > 1 ? false : true;

    }



    // 传递参数

    // 1. 传入根节点

    // 2. 返回深度

    private static int deep(TreeNode root) {

        // 退出条件

        // 空节点的深度为0

        if (null == root) {

            return 0;

        }

        // 单层逻辑

        // 深度=Max(左节点深度,右节点深度)+1

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

    }

    public static void main(String[] args) {

        TreeNode root = new TreeNode();

        root.val = 3;



        root.left = new TreeNode();

        root.left.val = 9;



        root.right = new TreeNode();

        root.right.val = 20;



        root.right.left = new TreeNode();

        root.right.left.val = 15;



        root.right.right = new TreeNode();

        root.right.right.val = 7;



        boolean b = isBalanced(root);

        System.out.println("第一棵树是平衡二叉树：" + b);



        TreeNode root1 = new TreeNode();

        root1.val = 1;



        root1.left = new TreeNode();

        root1.left.val = 2;



        root1.right = new TreeNode();

        root1.right.val = 2;



        root1.left.left = new TreeNode();

        root1.left.left.val = 3;



        root1.left.right = new TreeNode();

        root1.left.right.val = 3;



        root1.left.left.left = new TreeNode();

        root1.left.left.left.val = 4;



        root1.left.left.right = new TreeNode();

        root1.left.left.right.val = 4;



        boolean b1 = isBalanced(root1);

        System.out.println("第二棵树是平衡二叉树：" + b1);

    }

}





class TreeNode{

    int val;

    TreeNode left;

    TreeNode right;

}