首页 > 其他分享 >判断是不是平衡二叉树

判断是不是平衡二叉树

时间:2023-01-09 23:23:03浏览次数:38  
标签:right const 是不是 depth 二叉树 平衡 root

题目描述

输入一棵节点数为 n 二叉树,判断该二叉树是否是平衡二叉树。
在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树
平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

思路分析

  • 定义一个求二叉树高度的函数depth
  • 先处理特殊情况,空树,为平衡树
  • root为根节点的左右子树差 ≤ 1 → 继续向下判断子树是否满足条件,直到树中每个节点都判断完成 → 确定为一颗平衡二叉树
  • root为根节点的左右子树差 > 1 → 非平衡

代码参考

function IsBalanced_Solution (pRoot) {
  // write code here
  const depth = (root) => {
    if (!root) return 0
    const left = depth(root.left)
    const right = depth(root.right)
    return Math.max(left, right) + 1
  }
  if (!pRoot) return true
  const gap = Math.abs(depth(pRoot.right) - depth(pRoot.left))
  if (gap <= 1) return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)
  else return false
}

标签:right,const,是不是,depth,二叉树,平衡,root
From: https://www.cnblogs.com/zx529/p/17038842.html

相关文章

  • 判断是不是完全二叉树
    题目要求给定一个二叉树,确定他是否是一个完全二叉树。完全二叉树的定义:若二叉树的深度为h,除第h层外,其它各层的结点数都达到最大个数,第h层所有的叶子结点都连续集中......
  • Spring Boot 3.0横空出世,快来看看是不是该升级了
    目录简介对JAVA17和JAVA19的支持recordTextBlocksSwitchExpressionsinstanceof模式匹配SealedClassesandInterfaces迁移到JakartaEEGraalVMNativeImageSupport对M......
  • 二叉树由前序遍历和中序遍历求后序遍历
    题目:二叉树遍历问题描述给定一棵二叉树的先序遍历和中序遍历序列,求其后序遍历序列。输入格式输入数据有两行,为两个字符串,其长度n均小于等于26。第一行为先序遍历序......
  • 二叉树递归模板总结
    101.对称二叉树boolisQ(TreeNode*root1,TreeNode*root2){if(root1==nullptr&&root2==nullptr){returntrue;}elseif(roo......
  • leetcode-671. 二叉树中第二小的节点
    dfs取左右子树第二大的值进行比较/***Definitionforabinarytreenode.*typeTreeNodestruct{*Valint*Left*TreeNode*Right*TreeNod......
  • 101. 对称二叉树
    101.对称二叉树难度简单2227收藏分享切换为英文接收动态反馈给你一个二叉树的根节点root,检查它是否轴对称。示例1:输入:root=[1,2,2,3,4,4,3]输出:true示例2:......
  • LeetCode 236_二叉树的最近公共祖先
    LeetCode236:二叉树的最近公共祖先题目给定一个二叉树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树T的两个节点p、q,最近......
  • 二叉树 LC104.MaxDepth of Binary Tree
    最近看了labuladong讲二叉树,掌握了一种思路:拿到二叉树题目,思考三个维度——能不能遍历一遍就得出结果?如果可以,配合一个traverse函数+外部变量进行实现。——能不能定义......
  • 【C语言 数据结构】二叉树
    文章目录​​二叉树​​​​一、二叉树的概念​​​​二、二叉树的基本形态​​​​三、二叉树的性质​​​​四、特殊的二叉树​​​​五、二叉树的存储结构​​​​5.1......
  • 每日算法之在二叉树中找到两个节点的最近公共祖先
    JZ86在二叉树中找到两个节点的最近公共祖先题目给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值o1和o2,请找到o1和o2的最近公共祖先节点。注:本题保......