文档章节

判断二叉树是不是平衡的

datacube
 datacube
发布于 2016/07/06 17:11
字数 185
阅读 10
收藏 1
public class IsBalanceTree {
    public static void main(String[] args) {
        IsBalanceTree bt = new IsBalanceTree();
        TreeNode root = new TreeNode(1);
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(1);
        TreeNode n3 = new TreeNode(1);
//        TreeNode n4 = new TreeNode(1);
        root.left = n1;
        root.right = n2;
        n1.left = n3;
//        n3.left = n4;
//        System.out.println(bt.getHeight(root));
        System.out.println(bt.isBalance(root));
    }

    int getHeight(TreeNode root){
        if (root == null) return 0;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        //return left > right?(left+1):(right +1);
        return 1 + Math.max(left, right);
    }

    boolean isBalance(TreeNode root){
        if (root == null) return true;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        if (left - right > 1 || left - right < -1){
            return false;
        }
        return isBalance(root.left) && isBalance(root.right);
    }
}

© 著作权归作者所有

下一篇: 递归-汉诺塔
datacube
粉丝 9
博文 607
码字总数 152394
作品 0
海淀
程序员
私信 提问
十小时搞定二叉树面试之DFS方法(Python)

数据工程师惯用python,然而数据结构还是c++或者java比较经典。这就造成很多朋友并不太习惯。本文就从《剑指offer》这本书中的经典题型出发,来研究探讨一下python 刷数据结构题型的一些惯用...

香橙云子
09/01
0
0
110. Balanced Binary Tree - LeetCode

Question 110. Balanced Binary Tree Solution 题目大意:判断一个二叉树是不是平衡二叉树 思路:定义个boolean来记录每个子节点是否平衡 Java实现: Ref https://www.youtube.com/watch?v=...

yysue
2018/08/15
34
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
2018/09/04
0
0
[剑指offer] 平衡二叉树

本文首发于我的个人博客:尾尾部落 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 解题思路 定义:平衡二叉查找树,简称平衡二叉树。 可以是空树。 假如不是空树,任何一个结点的...

繁著
2018/08/08
0
0
数据结构与算法之10(AVL自平衡二叉树与RB红黑树)

本节继续总结二叉树的变种,上节里的哈夫曼树是一种独特的二叉树,用于编解码会比较有效。这里的两种树都是BST二叉搜索树的加强版。 》BST二叉搜索树的弱点 我们之前也提到了,当插入序列是有...

kkae8643150
2017/12/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Mybatis Plus删除

/** @author beth @data 2019-10-17 00:30 */ @RunWith(SpringRunner.class) @SpringBootTest public class DeleteTest { @Autowired private UserInfoMapper userInfoMapper; /** 根据id删除......

一个yuanbeth
33分钟前
4
0
总结

一、设计模式 简单工厂:一个简单而且比较杂的工厂,可以创建任何对象给你 复杂工厂:先创建一种基础类型的工厂接口,然后各自集成实现这个接口,但是每个工厂都是这个基础类的扩展分类,spr...

BobwithB
今天
4
0
java内存模型

前言 Java作为一种面向对象的,跨平台语言,其对象、内存等一直是比较难的知识点。而且很多概念的名称看起来又那么相似,很多人会傻傻分不清楚。比如本文我们要讨论的JVM内存结构、Java内存模...

ls_cherish
今天
4
0
友元函数强制转换

友元函数强制转换 p522

天王盖地虎626
昨天
5
0
js中实现页面跳转(返回前一页、后一页)

本文转载于:专业的前端网站➸js中实现页面跳转(返回前一页、后一页) 一:JS 重载页面,本地刷新,返回上一页 复制代码代码如下: <a href="javascript:history.go(-1)">返回上一页</a> <a h...

前端老手
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部