logo

  • 首页
  • 博客简介
  • 说说页面
  • 关于
  • 文章存档
    • C#教程
    • C#实战
  • 隐私政策
  • 首页
  • 博客简介
  • 说说页面
  • 关于
  • 文章存档
  • 隐私政策
您正在使用IE浏览器,部分内容可能无法显示,建议您换用更新的浏览器,请单击下载Chrome浏览器
显示屏过小,本网站无法正常显示
你处于离线状态,正在显示缓存网页
首页/ 分类:信奥/ 【信奥】判断平衡二叉树

【信奥】判断平衡二叉树

2020年7月23日 14:06:09 吕舒君 0 百度已收录 618 次浏览

题面

输出

给定一个二叉树,判断它是否平衡。若平衡,则打印字符串"yes",若不平衡,则打印字符串"no"。

平衡二叉树的定义是:一棵二叉树中每个节点的两个子树的高度之差不超过1。

输入

第一行一个正整数n,表示结点的个数

n行,第i行第一个数l表示第i个结点左孩子的序号,第二个数r表示第i个结点右孩子的序号,-1表示空

描述

若平衡,则打印字符串"yes",若不平衡,则打印字符串"no"。

思路

如上一题,【信奥】求树的高度,可以先求出树的高度后,判断左右子树的绝对值是否大于1,对应输出yes、no。注意打flag,避免多次判断。

最终代码

#include<bits/stdc++.h>
  using namespace std;
  struct node
  {
  	int val;
  	int l, r;
  };
  unordered_map<int,node> tree;
  int n;
  int ans=INT_MIN;
  bool flag=1;
  int geth(int root)
  {
  	if (root == -1) return 0;
  	int ll=geth(tree[root].l);
  	int rr=geth(tree[root].r);
  	int tmp = max(ll,rr)+1;
  	if(abs(ll-rr)>1&&flag==1)
  	{
  		cout<<"no";
  		flag=0;
  	}
  	return tmp;
  }
  int main()
  {
  	cin >> n;
  	for (int i = 1; i <= n; i++)
  	{
  		scanf("%d %d", &tree[i].l, &tree[i].r);
  	}
  	geth(1);
  	if(flag)
  	{
  		cout<<"yes";
  	}
  	return 0;
  }
作者头像
吕舒君
就是本站站长(^_−)☆
提示
你已经点赞过了
上一篇文章缩略图
【信奥】求树的高度
« 上一篇文章
下一篇文章缩略图
【信奥】收集树叶
下一篇文章 »
原创声明
版权声明: 本文由作者吕舒君于2020年7月23日 14:06:09原创发表.
转载请务必取得作者同意, 并附带本页面地址: https://cszj.wang/1487.html
查看作者 吕舒君 的所有文章
发表评论
account_circle
email
email
评论区
共0条回复
暂无评论,说说你的看法吧!
侧边栏
文章目录
  • 题面
  • 输出
  • 输入
  • 描述
  • 思路
  • 最终代码
最近文章
文章缩略图
【Windows】Windows11初体验
升级&安装 不久前,微软刚刚发布了“十年来最重要的操
文章缩略图
【Windows】如何关闭Windows的自动更新
引子 Windows的自动更新的问题已经困扰了一些用户很久了
文章缩略图
【前端教程】如何创建一个属于自己的在线思维导图网站
什么是思维导图 思维导图,英文是The Mind Map,又
文章缩略图
【信奥】Java vs C++
题面 题目描述 Java和C++两种语言的辩手都可以相互争论
文章缩略图
【信奥】收集树叶
题面 描述 给出一棵二叉树,收集并移除所有叶子,重复执行,直
最近文章
您尚未登录
底部推荐
随机文章
文章缩略图
【Windows】Windows11初体验
升级&安装 不久前,微软刚刚发布了“十年来最重要的操
站点统计
文章总数:35篇
评论总数:127条
分类总数:9个
标签总数:81个
网站运行:1995天
最后更新:2022-4-4
友情链接
搜索站 文件管理 洛谷 WordPress大学

吕舒君的博客,一个传递知识的网站!

前往本站
吕舒君的博客
一个传递知识的网站

版权所有·吕舒君(2016-2022)

酷博客(V4.1.0). Theme By 吕舒君. 网站已使用SSL加密 本页面进行了 54 次请求在 0.306 秒内加载完成, 使用了 11.80MB 的内存。