题面

输出

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