剑指Offer | 平衡二叉树

墨蓝 2022-05-23 05:53 143阅读 0赞

做了个剑指Offer的题目目录，链接如下：  
[https://blog.csdn.net/mengmengdastyle/article/details/80317246][https_blog.csdn.net_mengmengdastyle_article_details_80317246]

## 一、题目 ##

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

## 二、讲解 ##

（1）平衡二叉树  
平衡二叉树（Balanced Binary Tree）又被称为**AVL**树（有别于AVL算法），且具有以下性质：

*  它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
 *  并且左右两个子树都是一棵平衡二叉树。

这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。  
（2）  
递归去判断

## 三、代码 ##

public class Solution {
       public boolean IsBalanced_Solution(TreeNode root) {
            if (root == null)
                return true;
    
            if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1)
                return false;
    
    
            return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    
        }
    
        public int getHeight(TreeNode root) {
            if (root == null)
                return 0;
            return max(getHeight(root.left), getHeight(root.right)) + 1;
        }
    
        private int max(int a, int b) {
            return (a > b) ? a : b;
        }
    }

[https_blog.csdn.net_mengmengdastyle_article_details_80317246]: https://blog.csdn.net/mengmengdastyle/article/details/80317246

发表评论取消回复

表情：

评论列表（有 0 条评论，143人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer 平衡二叉树

[剑指offer题型分类及各题的代码及解题思路][offer] 1、题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。 2、初始结构定义如下： ...

女爷i/ 2024年04月17日 06:00/ 0 赞/ 34 阅读

相关剑指 Offer 55 - II. 平衡二叉树 || 110. 平衡二叉树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

以你之姓@/ 2022年11月05日 03:19/ 0 赞/ 140 阅读

相关剑指offer 平衡二叉树

1.题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。 2.分析平衡二叉树在leetcode刷题时也做过，附上[题目链接][Link 1] 之前写的解题

灰太狼/ 2022年06月15日 05:21/ 0 赞/ 143 阅读

相关剑指Offer | 平衡二叉树

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

墨蓝/ 2022年05月23日 05:53/ 0 赞/ 144 阅读

相关剑指offer 平衡二叉树

题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。解题思路平衡二叉树是这样定义的：平衡二叉树（Balanced Binary Tree）又被称为A

电玩女神/ 2022年05月21日 05:18/ 0 赞/ 150 阅读

相关【剑指Offer】39平衡二叉树

题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。时间限制：1秒；空间限制：32768K；本题知识点：树解题思路需要用到查找二叉树深度的函数，根据平

绝地灬酷狼/ 2022年05月12日 13:42/ 0 赞/ 147 阅读

相关剑指offer:平衡二叉树

题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。 AC C++ Solution: 递归判断左右子树的高度差并记录高度返回给父节点 class So

迈不过友情╰/ 2022年04月10日 09:15/ 0 赞/ 167 阅读

相关【剑指Offer】（树）平衡二叉树

题目链接：[https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11

比眉伴天荒/ 2022年03月16日 01:12/ 0 赞/ 163 阅读

相关剑指Offer-平衡二叉树

题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。平衡二叉树的定义为：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

刺骨的言语ヽ痛彻心扉/ 2022年02月19日 11:43/ 0 赞/ 167 阅读

相关 [剑指offer]平衡二叉树

输入一棵二叉树，判断该二叉树是否是平衡二叉树。 class Solution { public: //后序遍历 bool IsB

本是古典何须时尚/ 2021年11月22日 09:44/ 0 赞/ 282 阅读