题面

输出

给定一个二叉树，判断它是否平衡。若平衡，则打印字符串”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;
}