算法——是否为平衡二叉树

2022-3-2 diaba 算法 

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

« 算法——拿纸牌，最大积分是多少 | 算法——汉诺塔»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022