草庐IT

每日算法之判断是不是平衡二叉树

loongnuts 2023-04-18 原文

JZ79 判断是不是平衡二叉树

描述

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

思路

左右两个子树的高度差的绝对值不超过1
左右两个子树都是一棵平衡二叉树

代码

package esay.JZ79判断是不是平衡二叉树;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    //自顶向下
    /*public boolean IsBalanced_Solution(TreeNode root) {
        //空树也是平衡二叉树
        if (root == null) return true;
        //左子树深度
        int left = deep(root.left);
        //右子树深度
        int right = deep(root.right);
        if (left - right > 1 || right - left > 1) return false;

        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }


    public int deep (TreeNode node) {
        if (node == null) return 0;
        //左遍历
        int left = deep(node.left);
        //右遍历
        int right = deep(node.right);
        return left > right ? left + 1 :right + 1;
    }*/

    //自底向上
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) return true;
        return getdepth(root) != -1;
    }


    public int getdepth (TreeNode node) {
        if (node == null) return 0;
        //左遍历
        int left = getdepth(node.left);
        if (left < 0) return -1;
        //右遍历
        int right = getdepth(node.right);
        if (right < 0) return -1;
        return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
    }


}
每日判断rightleftreturnJava

有关每日算法之判断是不是平衡二叉树的更多相关文章

  1. ruby - 匹配未转义的平衡定界符对 - 2

    如何匹配未被反斜杠转义的平衡定界符对(其本身未被反斜杠转义)(无需考虑嵌套)？例如对于反引号，我试过了，但是转义的反引号没有像转义那样工作。regex=/(?!$1:"how\\"#expected"how\\`are"上面的正则表达式不考虑由反斜杠转义并位于反引号前面的反斜杠，但我愿意考虑。StackOverflow如何做到这一点？这样做的目的并不复杂。我有文档文本，其中包括内联代码的反引号，就像StackOverflow一样，我想在HTML文件中显示它，内联代码用一些spanMaterial装饰。不会有嵌套，但转义反引号或转义反斜杠可能出现在任何地方。

  2. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  3. 【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2

    HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

  4. ruby-on-rails - 只有当不是 nil 时才执行映射？ - 2

    如果names为nil，则以下中断。我怎样才能让这个map只有在它不是nil时才执行？self.topics=names.split(",").mapdo|n|Topic.where(name:n.strip).first_or_create!end 最佳答案 其他几个选项:选项1(在其上执行map时检查split的结果):names_list=names.try(:split,",")self.topics=names_list.mapdo|n|Topic.where(name:n.strip).first_or_create!e

  5. ruby-on-rails - Rails 格式验证——字母数字，但不是纯数字 - 2

    什么是测试格式验证的最佳方法让我们说一个用户名，使用字母数字的正则表达式，但不是纯数字？我一直在我的模型中使用以下验证validates:username,:format=>{:with=>/^[a-z0-9]+[-a-z0-9]*[a-z0-9]+$/i}数字用户名(例如“342”)通过了验证，这是我不想要的。 最佳答案 您想“向前看”一封信:/\A(?=.*[a-z])[a-z\d]+\Z/i 关于ruby-on-rails-Rails格式验证——字母数字，但不是纯数字，我们在Sta

  6. ruby - 强制浏览器下载文件而不是打开文件 - 2

    我要下载http://foobar.com/song.mp3作为song.mp3，而不是让Chrome在其native中打开它浏览器中的播放器。我怎样才能做到这一点？ 最佳答案 您只需要确保发送这些header:Content-Disposition:attachment;filename=song.mp3;Content-Type:application/octet-streamContent-Transfer-Encoding:binarysend_file方法为您完成:get'/:file'do|file|file=File.

  7. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  8. ruby - 更改 $LOAD_PATH 时，为什么使用 unshift 而不是 push？ - 2

    我发现ruby加载路径是一个数组，很多项目都是这样使用的:$:.unshift(File.expand_path("../../lib",__FILE__))可以将本地文件添加到ruby路径数组的前面，方便我们require或者load。所以，我希望知道为什么我们不使用push将文件添加到数组的末尾？ 最佳答案 假设您有一个“date.rb”文件(为什么不呢)并且您想要加载这个文件，而不是标准库日期。如果您使用追加，当您调用require'date'时您的文件将永远不会被加载，因为它位于数组的末尾并且标准日期会在之前找到。因此，如果

  9. ruby - 如何排序不是简单的哈希(哈希的哈希) - 2

    我有一个这样的哈希{55=>{:value=>61,:rating=>-147},89=>{:value=>72,:rating=>-175},78=>{:value=>64,:rating=>-155},84=>{:value=>90,:rating=>-220},95=>{:value=>39,:rating=>-92},46=>{:value=>97,:rating=>-237},52=>{:value=>73,:rating=>-177},64=>{:value=>69,:rating=>-167},86=>{:value=>68,:rating=>-165},53=>{:va

  10. ruby - Unicorn 使用 `reload` 而不是 `restart`？ - 2

    我在这里对我的部署策略有点困惑，在什么情况下部署时我想向unicorn发送reload信号？例如在我的例子中它会是这样的:sudokill-sUSR2`cat/home/deploy/apps/my_app/current/tmp/pids/unicorn.pid`我一直在通过杀死那个pid来部署我的应用程序，然后通过类似的东西再次启动unicorn:bundleexecunicorn-cconfig/unicorn/production.rb-Eproduction-D我只是想知道为什么要使用重新加载？我可以通过这样做获得部署的任何性能吗？ 最佳答案

随机推荐