PAT 1110

PAT 1102的变形,注意1110需要支持2位数操作,层序遍历的时候检查中间是否有缺漏结点就可以了

#include <iostream>#include <string>#include <cstring>#include<algorithm>#include<cmath>#include <vector>#include <map>#include<stack>#include<queue>#include <stdio.h>using namespace std;#define MAX 20000+5#define INF 0x3f3f3f3fstruct BTree {	int lchild, rchild;}t[MAX];int n;int main(){	int  i, root = -1;	int node[250];	char c1[10], c2[10];	scanf("%d", &n);	memset(node, 0, sizeof(node));	for (i = 0; i < n; i++) {		cin >> c1 >> c2;		if (c1[0] == '-') {			t[i].lchild = -1;		}		else {			sscanf(c1, "%d", &t[i].lchild);			node[t[i].lchild] = 1;		}		if (c2[0] == '-') {			t[i].rchild = -1;		}		else {			sscanf(c2, "%d", &t[i].rchild);			node[t[i].rchild] = 1;		}	}	for (i = 0; i < n; i++) {		if (node[i] == 0) {			root = i;			break;		}	}	queue<int>q;	int cnt = 1, flag = 0, tmp;	q.push(root);	while (!q.empty()) {		tmp = q.front();		q.pop();		if (t[tmp].lchild == -1) {			flag = 1;			break;		}		q.push(t[tmp].lchild);		cnt++;		if (cnt == n)			break;		if (t[tmp].rchild == -1) {			flag = 1;			break;		}		q.push(t[tmp].rchild);		cnt++;		if (cnt == n)			break;	}	if (n == 1) {		PRintf("YES 0/n");		return 0;	}	if (flag)		printf("NO %d/n", root);	else		printf("YES %d/n", t[tmp].rchild == -1 ? t[tmp].lchild : t[tmp].rchild);	return 0;}