【信奥】判断平衡二叉树

题面

输出

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