判断二叉树是否是平衡二叉树

àì夳堔傛蜴生んèń 2022-04-18 01:47 295阅读 0赞

平衡二叉搜索树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

思路：如果一颗二叉树的所有子树都是平衡二叉树，它一定是平衡二叉树。

#include <bits/stdc++.h>
    using namespace std;
    typedef struct BNode* BTree;
    struct BNode
    {
        
        int data;
        BTree left;
        BTree right;
    };
    
    void Insert(BTree &t,int data){
        
        if(!t){
        
            BTree p=(BTree)malloc(sizeof(BTree));
            p->data=data;
            p->left=NULL;
            p->right=NULL;
            t=p;
        }
        else if(data<t->data)Insert(t->left,data);
        else if(data>=t->data)Insert(t->right,data);
    }
    
    bool IsBalanceTree(BTree root, int &depth)
        {
        
            if (root == NULL){
        
                depth = 0;
                return true;
            }
            int ldepth = 0,rdepth=0;
            if (!IsBalanceTree(root->left, ldepth)||!IsBalanceTree(root->right, rdepth)){
        
                return false;
            }
            depth = rdepth > ldepth ? rdepth + 1 : ldepth + 1;
            return abs(ldepth - rdepth) < 2;
        }
    int main()
    {
        
        int n,depth;
        int a[1001];
        cin>>n;
        BTree t=NULL;
        for(int i=0;i<n;i++){
        
            cin>>a[i];
            Insert(t,a[i]);
        }
        if(IsBalanceTree(t,depth))cout<<"YES"<<" "<<depth<<endl;
        else cout<<"NO"<<endl;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 N39_判断该二叉树是否是平衡二叉树。

题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。 package new_offer; / 输入一棵二叉树，判断该二叉树是否是平衡二

矫情吗；*/ 2023年08月17日 17:36/ 0 赞/ 118 阅读

相关【算法】判断二叉树是否是平衡二叉树

问题：判断一个二叉树是否是平衡二叉树。分析：平衡二叉树要求左子树和右子树的高度相差为1，且左右子树都是平衡二叉树。递归可以很好的解决这个问题。但是首先要求树的深度。代码

迈不过友情╰/ 2022年08月09日 05:08/ 0 赞/ 237 阅读

相关判断二叉树是不是平衡二叉树

输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。例如下图中的二叉树就是一棵平衡二叉树： ![C

ゞ浴缸里的玫瑰/ 2022年08月02日 04:49/ 0 赞/ 215 阅读

相关判断二叉树是否是平衡树

面试题39：输入一颗二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中节点的左右子树的深度相差不超过1，那么它就是一颗平衡二叉树 //判断二叉树是不是平衡树

「爱情、让人受尽委屈。」/ 2022年06月17日 07:08/ 0 赞/ 230 阅读

相关平衡二叉树判断、完全二叉树判断

平衡二叉树判断完全二叉树判断 -------------------- 平衡二叉树判断有一棵二叉树，请设计一个算法判断这棵

逃离我推掉我的手/ 2022年06月09日 09:36/ 0 赞/ 343 阅读

相关判断一棵二叉树是否是平衡二叉树

![这里写图片描述][70] class TreeNode { int val = 0; TreeNode left = null;

た入场券/ 2022年05月25日 12:44/ 0 赞/ 253 阅读

相关判断二叉树是否是对称二叉树

![这里写图片描述][70] import java.util.; class TreeNode { int val = 0;

约定不等于承诺〃/ 2022年05月24日 07:43/ 0 赞/ 250 阅读

相关判断二叉树是否是平衡二叉树

平衡二叉搜索树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。思路：如

àì夳堔傛蜴生んèń/ 2022年04月18日 01:47/ 0 赞/ 296 阅读

相关判断二叉树是否是二叉搜索树

问题给定一棵二叉树，判定该二叉树是否是二叉搜索树（Binary Search Tree）？解法1:暴力搜索首先说明一下二叉树和二叉搜索树的区别。二叉树指这

ゝ一世哀愁。/ 2021年12月21日 07:39/ 0 赞/ 270 阅读

相关【数据结构】（平衡二叉树）判断二叉树是否是平衡二叉树

> 算法思想：判断一棵树是否为平衡二叉树可以采取高度差的递归方式来判断这个方法比较简单但是复杂度较高（因为高度被重复计算了很多次）O（nlogn） //递归求高度

短命女/ 2021年10月29日 14:50/ 0 赞/ 400 阅读