剑指offer 平衡二叉树

女爷i 2024-04-17 06:00 63阅读 0赞

# [剑指offer题型分类及各题的代码及解题思路][offer] #

## 1、题目描述 ##

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

## 2、初始结构定义如下： ##

class Solution {
    public:
        bool IsBalanced_Solution(TreeNode* pRoot) {}
    };

## 3、思路 ##

每个结点最好只遍历一遍，减小复杂度。

我们可以用后序遍历的方式来遍历二叉树的每个结点，在遍历一个结点之前，我们就已经遍历了它的左右子树，只要在遍历每个节点的时候记录他的深度，我们就可以一边遍历一边判断每个结点是否平衡。

注：所谓平衡，即左右子树的深度差绝对值不大于1。

## 4、C++实现代码如下 ##

class Solution 
    {
    public:
        bool IsBalanced_Solution(TreeNode* pRoot) 
        {
            int depth = 0;
            return IsBalanced(pRoot, &depth);
        }
        
        bool IsBalanced(TreeNode* pRoot, int* d)
        {
            if(pRoot == NULL)
            {
                *d = 0;
                return true;
            }
            
            int left,right;
            if(IsBalanced(pRoot->left, &left) && IsBalanced(pRoot->right, &right))
            {
                int diff = left - right;
                if(diff >= -1 && diff <= 1)
                {
                    *d = 1 + (left > right ? left : right);
                    return true;
                }
            }
            return false;
        }
    };

[offer]: https://blog.csdn.net/qq_26079093/article/details/96605538

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关剑指offer 平衡二叉树

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

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

相关剑指Offer | 平衡二叉树

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

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

相关剑指offer 平衡二叉树

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

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

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

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

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

相关剑指offer:平衡二叉树

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

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

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

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

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

相关剑指Offer-平衡二叉树

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

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

相关剑指Offer（java）判断平衡二叉树

题目输入一棵二叉树，判断该二叉树是否是平衡二叉树。解析预备知识平衡二叉树：它是一棵空树，或者它的左右子树的高度差不超过1，同时它的左右子树为一棵二叉树。而衡

末蓝、/ 2021年12月24日 00:03/ 0 赞/ 239 阅读

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

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

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