leetcode110 Balanced Binary Tree

题目

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. 一棵平衡二叉树即一棵二叉树的所有节点的左右子树的高度差不超过1.

解题思路

很显然,解这道题需要从得到二叉树的高度的算法修改而来。 获取二叉树的高度的算法:

private int height(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            int i = height(node.left);
            int j = height(node.right);
            return (i < j) ? j + 1 : i + 1;
        }
    }

只需要修改下,让树的左右子树的高度差大于1时,返回-1.

public class leetcode110 {
    public boolean isBalanced(TreeNode root) {
        int res = helper(root);
        return res != -1;
    }

    private int helper(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            int i = helper(node.left);
            int j = helper(node.right);
            if (i == -1 || j == -1)
                return -1;
            else {
                if (Math.abs(i - j) > 1) return -1;
                else
                    return Math.max(i, j) + 1;
            }
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏郭耀华‘s Blog

数据结构二叉树知识点总结

术语  1. 节点的度:一个节点含有的子树的个数称为该节点的度; 2. 叶节点或终端节点:度为零的节点;  3. 非终端节点或分支节点:度不为零的节点;  4....

29413
来自专栏彭湖湾的编程世界

【算法】论平衡二叉树(AVL)的正确种植方法

《算法(java)》                           — — Robert Sedgewick, Kevin Wayne

992
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题39二叉树的深度

题目:输入一颗二叉树的根结点,求该树的深度。从根结点到叶结点一次经过的结点形成树的一条路径,最长路径的长度为树的深度。 分析:本题是一道典型的“分治法”。要...

2995
来自专栏编程理解

数据结构(四):平衡二叉树(AVL树)

。影响时间复杂度的因素即为二叉树的高,为了尽量避免树中每层上只有一个节点的情况,这里引入平衡二叉树。

2643
来自专栏编程理解

数据结构(六):红黑树

级别的查询、插入和删除节点复杂度。相对于 AVL 树单纯的对每个节点的平衡因子进行判断,红黑树给节点赋予了颜色属性,并通过对树中节点的颜色进行限制,来保持整棵...

1592
来自专栏熊二哥

深入入门系列--Data Structure--04树

终于有机会重新回头学习一下一直困扰自身多年的数据结构了,赶脚棒棒哒。一直以来,对数据结构的掌握基本局限于线性表,稍微对树有一丢丢了解,而对于图那基本上就是不懂(...

1839
来自专栏向治洪

ArrayList和LinkedList的区别

一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构...

1919
来自专栏软件开发 -- 分享 互助 成长

二叉排序树和平衡二叉树

二叉排序树又称二叉查找树或二叉搜索树。 它一棵空树或者是具有下列性质: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,...

20310
来自专栏曾大稳的博客

树(Tree)以及二叉树的遍历

树(tree) 是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次...

1481
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题39判断平衡二叉树(高效方法)

题目:输入一颗二叉树的根结点,判断该树是不是平衡二叉树。 如果某二叉树中任意结点的左右子树的高度相差不超过1,那么它就是一棵平衡二叉树。 分析:所谓平衡二...

3658

扫码关注云+社区