本文最后更新于 1050 天前,其中的信息可能已经有所发展或是发生改变。
题面
输出
给定一个二叉树,判断它是否平衡。若平衡,则打印字符串”yes”,若不平衡,则打印字符串”no”。
平衡二叉树的定义是:一棵二叉树中每个节点的两个子树的高度之差不超过1。
输入
第一行一个正整数n,表示结点的个数
n行,第i行第一个数l表示第i个结点左孩子的序号,第二个数r表示第i个结点右孩子的序号,-1表示空
描述
若平衡,则打印字符串”yes”,若不平衡,则打印字符串”no”。
最终代码
#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; }