【信奥】判断平衡二叉树

1,153次阅读
没有评论

共计 667 个字符,预计需要 2 分钟阅读。

题面

输出

给定一个二叉树,判断它是否平衡。若平衡,则打印字符串”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;
}
正文完
 
再看一点
lvshujun
版权声明:本站原创文章,由 lvshujun 于2020-06-09发表,共计667字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请联系站长并注明出处。
评论(没有评论)