首页 > 其他分享 >剑指 Offer 55 - II. 平衡二叉树

剑指 Offer 55 - II. 平衡二叉树

时间:2023-04-25 12:24:41浏览次数:39  
标签:TreeNode Offer 55 II 二叉树 null root

剑指 Offer 55 - II. 平衡二叉树

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回 true

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回 false

限制:

  • 0 <= 树的结点个数 <= 10000

解法:递归,分解大问题为许多子问题。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(height(root.left)-height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    public int height(TreeNode root) {
        if (root == null) return 0;
        return Math.max(height(root.right),height(root.left))+1;
    }
}

 

标签:TreeNode,Offer,55,II,二叉树,null,root
From: https://www.cnblogs.com/fulaien/p/17352235.html

相关文章

  • 剑指 Offer 10- II. 青蛙跳台阶问题
    分析:因为好久没有练习思维还没有转变,所以这道题思考有点慢首先还是建立状态,到达第i级台阶时,有f[i]种跳法最后答案f[n-1]再状态转移,f[i]=f[i-1]+f[i-2] 赋初值,因为可以选择跳一阶或者两阶,所以初始赋值f[0]和f[1],f[0]=1,f[1]=2然后编写代码,但是最后有个问题,不知道1e9+7不是......
  • 剑指 Offer II 088. 爬楼梯的最少成本
    剑指OfferII088.爬楼梯的最少成本-力扣(LeetCode)分析:先思考建立状态。到达第i阶台阶时,花费最少体力为f[i]。再状态转移,到达i时有两种选择,从i-1或者i-2到i,两者取最小的再加上i需要花费的体力cost[i]。结果f[-1]最后得出状态转移:f[i]=min(f[i-1],f[i-1])+cost[i]......
  • LeetCode 40.组合总和II
    1.题目:给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次 。注意:解集不能包含重复的组合。示例 1:输入:candidates= [10,1,2,7,6,1,5],target= ......
  • day55(2023.4.24)
    1.应用程序分层 应用程序分层实现在分层项目中实现查询业务UserDao接口 UserDaoImpl接口实现类 UserService接口 UserServiceImpl接口实现类 web 此时数据库中的数据 运行结果2.封装通用的BaseDao封装通用的DML操作BaseDao接口 BaseDaoImpl接......
  • ASUS PRIME B550M-A (WI-FI) AMD Ryzen 3600电脑 Hackintosh 黑苹果efi引导文件
    原文来源于黑果魏叔官网,转载需注明出处。(下载请直接百度黑果魏叔)硬件型号驱动情况主板ASUSPRIMEB550M-A(WI-FI)处理器AMDRyzen3600已驱动内存16GB2933hz已驱动硬盘MidasForce1TBSSDNVMEM.2Gen3x42280FormFactor已驱动显卡AMDRX6600-XT已驱动声卡瑞昱@英特尔......
  • leetcode 550 游戏玩法分析IV
    游戏玩法分析 selectround(avg(a.event_dateisnotnull),2)asfractionfrom(selectplayer_id,min(event_date)asevent_datefromactivitygroupbyplayer_id)aspleftjoinactivityasaonp.player_id=a.player_idanda.event_date=date_......
  • API接口item_get-获取lazada商品详情(num_iid宝贝ID、title商品标题、price价格、nick
    什么是API?API是一个缩写,它代表了一个pplicationPAGC软件覆盖整个房间。API是用于构建软件应用程序的一组例程,协议和工具。API指定一个软件程序应如何与其他软件程序进行交互。例行程序:执行特定任务的程序。例程也称为过程,函数或子例程。协议:在两个系统之间传输数据的格式。......
  • ASCII码图
    ASCII(AmericanStandardCodeforInformationInterchange,美国标准信息交换代码)是基于拉丁字母的一套电脑编码系统,主要用于显示现代英语和其他西欧语言。它是现今最通用的单字节编码系统,并等同于国际标准ISO/IEC646。作者:sunsky303......
  • 请求处理类 yii\web\Request
    $request=Yii::$app->request;//请求对象//$request->enableCsrfValidation=false;//取消CSRF验证$resolve=$request->resolve();//请求拆分$getHeaders=$request->getHeaders();//请求头集合$getMethod=$request->getMethod(......
  • 二叉树的遍历(递归算法)
    //二叉树的遍历(递归算法)#include<stdio.h>#include<malloc.h>typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;//存储二叉树的左孩子和右孩子}BiTNode,*BiTree;voidInitTree(BiTree&root){root=(BiTNode*)malloc(sizeof(BiTNo......