# 11211: 【原1211】isCBT

### 题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1211

## Sample Input1

``````4
0 0
0 0
1 0
3 2
``````

## Sample Output1

``````Y
``````

## Sample Input2

``````4
0 0
0 0
0 1
3 2
``````

## Sample Output2

``````N
``````

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/3/31.
//

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

template<typename Item>
class Queue {
class Node {
public:
Item item;
Node *next = nullptr;
};

int N;
Node *first;
Node *last;

public:
Queue() {
N = 0;
first = last = nullptr;
}

bool isEmpty() {
return N == 0;
}

int size() {
return N;
}

void enqueue(Item item) {
if (N == 0) {
first = new Node{item};
last = first;
} else {
Node *tmp = last;
last = new Node{item};
tmp->next = last;
}
++N;
}

Item dequeue() {
Item item = first->item;
Node *tmp = first;
first = first->next;
if (N == 1) last = nullptr;
delete tmp;
--N;
return item;
}

Item getFirst() {
return first->item;
}

Item getLast() {
return last->item;
}

virtual ~Queue() {
Node *tmp;
while (first != nullptr) {
tmp = first;
first = first->next;
delete tmp;
}
}
};

// template<typename Item>
class BinaryTree {

class Node {
public:
Node *left = nullptr, *right = nullptr;
Node *father = nullptr;
// Item val;
};

int size;
int maxSize;
Node *root;
Node **nodes;

public:
BinaryTree() {
BinaryTree(5);
}

explicit BinaryTree(int maxSize) {
root = nullptr;
this->maxSize = maxSize;
nodes = new Node *[maxSize + 1]{};
for (int i = 1; i <= maxSize; ++i) {
nodes[i] = new Node();
}
size = 0;
}

void add(int left, int right) {
if (size == maxSize) resize(maxSize * 2);
++size;

nodes[size]->left = nodes[left];
nodes[size]->right = nodes[right];
if (left) nodes[left]->father = nodes[size];
if (right) nodes[right]->father = nodes[size];
}

void resize(int newSize) {
auto oldNodes = nodes;
nodes = new Node *[newSize + 1]{};
for (int i = 1; i <= maxSize; ++i) {
nodes[i] = oldNodes[i];
}
for (int i = maxSize + 1; i <= newSize; ++i) {
nodes[i] = new Node;
}
maxSize = newSize;
}

void getRoot() {
Node *p = nodes[1];
while (p->father) {
p = p->father;
}
root = p;
}

bool isCBT() {
getRoot();

Queue<Node *> queue;
queue.enqueue(root);
Node *p;

while (p = queue.dequeue()) {
queue.enqueue(p->left);
queue.enqueue(p->right);
}

while (!queue.isEmpty()) {
if (p = queue.dequeue()) {
return false;
}
}
return true;
}

virtual ~BinaryTree() {
for (int i = 1; i <= maxSize; ++i) {
delete nodes[i];
}
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N;
cin >> N;
BinaryTree binaryTree(N);
int a, b;
for (int i = 0; i < N; ++i) {
cin >> a >> b;
}

cout << (binaryTree.isCBT() ? 'Y' : 'N') << endl;
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "cmath"
#include "cstring"
using namespace std;

template <class T>
class mQueue {
class node {
public:
T data;
node* next = nullptr;
};
* rear = nullptr;
size_t _size = 0;

public:
//构造函数
mQueue() {
}
//判断是否为空
bool empty() {
}
//增加
void push(const T& val) {
rear->next = new node;
rear = rear->next;
rear->data = val;
++_size;
}
//删除
void pop() {
//安全措施
return;
--_size;
}
//大小
size_t size() {
return _size;
}
//最前
T& front() {
//安全措施
}
//最后
T& back() {
//安全措施
return rear->data;
}
};

//二叉树类
template <class T>
class myBinaryTree {
public:
class node {
public:
T data;
node *lchild = nullptr, *rchild = nullptr,*parent=nullptr;
};
node *root = nullptr;
node **nodeList=nullptr;
int lengthOfNodeList=0;

//创建树
void createTree(int num) {
nodeList = new node*[num+1] {nullptr};
lengthOfNodeList = num;
}

void creadNode(int nodeNum, int lchild, int rchild) {
if(nodeList[nodeNum]==nullptr)
nodeList[nodeNum] = new node;

if (lchild != 0) {
if (nodeList[lchild] == nullptr)
nodeList[lchild] = new node;
nodeList[lchild]->parent = nodeList[nodeNum];
nodeList[nodeNum]->lchild = nodeList[lchild];
}

if (rchild != 0) {
if (nodeList[rchild] == nullptr)
nodeList[rchild] = new node;
nodeList[rchild]->parent = nodeList[nodeNum];
nodeList[nodeNum]->rchild = nodeList[rchild];
}
}

void checkRoot() {
for (int i = 1; i <= lengthOfNodeList; i++) {
if (nodeList[i]->parent == nullptr) {
root = nodeList[i];
break;
}
}
}

//清空
void clear() {
clear(root);
}

void clear(node *p) {
if (p == nullptr)
return;
clear(p->lchild);
clear(p->rchild);
delete p;
p = nullptr;
}

//构造
myBinaryTree() {}

//析构
~myBinaryTree() {
clear(root);
}

//判断是否非空
bool empty() {
return root == nullptr;
}

//判断是否为完全二叉树
bool isCBT() {
if (empty())
return false;
//层次遍历
mQueue<node*> treeQueue;
bool flag = false;
//先入队
treeQueue.push(root);

//反复
while (!treeQueue.empty()) {
//先出队一个
node* temp = treeQueue.front();
treeQueue.pop();

//右孩子有左孩子没有
if (temp->lchild == nullptr&&temp->rchild != nullptr)
return false;

if (!flag) {
//左孩子有右孩子没有
if (temp->lchild != nullptr&&temp->rchild == nullptr) {
flag = true;
//左孩子入队
treeQueue.push(temp->lchild);
}
//左右孩子都没有
else if (temp->lchild == nullptr&&temp->rchild == nullptr) {
flag = true;
}
//左右都有孩子
else {
treeQueue.push(temp->lchild);
treeQueue.push(temp->rchild);
}
}
else {
//判断是否为叶子
if (temp->lchild != nullptr || temp->rchild != nullptr)
return false;
}
}

return true;
}
};

int main() {
myBinaryTree<int> bTree;
int num;
cin >> num;
bTree.createTree(num);

for (int i = 1; i <= num; i++) {
int lchild, rchild;
scanf("%d %d", &lchild, &rchild);
}
bTree.checkRoot();
cout << (bTree.isCBT()?"Y":"N");

return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

const int maxN = 100000;

#include <iostream>

using namespace std;

template <class elemType>
class queue {
public:
virtual bool isEmpty() const = 0;
virtual void enQueue(const elemType &) = 0;
virtual elemType deQueue() = 0;
virtual elemType getHead() const = 0;
virtual ~queue() {}
};

template <class elemType>
class seqQueue : public queue<elemType> {
private:
elemType *data;
int maxSize;
int front, rear;
void doubleSpace();

public:
seqQueue(int size = maxN + 100);
~seqQueue();
bool isEmpty() const;
void enQueue(const elemType &);
elemType deQueue();
int length() const;
};

template <class elemType>
void seqQueue<elemType>::doubleSpace() {
elemType *tmp = data;
data = new elemType[maxSize * 2];

for (int i = 1; i <= maxSize; i++) {
data[i] = tmp[(front + i) % maxSize];
}

front = 0;
rear = maxSize;
maxSize *= 2;
delete[] tmp;
}

template <class elemType>
seqQueue<elemType>::seqQueue(int size) : maxSize(size), front(0), rear(0) {
data = new elemType[size];
}

template <class elemType>
seqQueue<elemType>::~seqQueue() {
delete[] data;
}

template <class elemType>
bool seqQueue<elemType>::isEmpty() const {
return front == rear;
}

template <class elemType>
void seqQueue<elemType>::enQueue(const elemType &x) {
if ((rear + 1) % maxSize == front) {
doubleSpace();
}
rear = (rear + 1) % maxSize;
data[rear] = x;
}

template <class elemType>
elemType seqQueue<elemType>::deQueue() {
front = (front + 1) % maxSize;
return data[front];
}

template <class elemType>
return data[(front + 1) % maxSize];
}

template <class elemType>
int seqQueue<elemType>::length() const {
return ((rear + maxSize - front) % maxSize);
}

template <class T>
class bTree {
private:
struct Node {
T data;
Node *left;
Node *right;
Node *parent;

Node(T d = 0, Node *p = 0, Node *l = 0, Node *r = 0)
: data(d), parent(p), left(l), right(r) {}
};
Node *nodes[maxN + 100];
void clear(Node *);

public:
Node *root;
bTree(int n = 10);
~bTree();
void findRoot();
void checkTree(int N, Node *p);
};

template <class T>
bTree<T>::bTree(int n) : root(NULL) {
for (int i = 0; i <= n; i++) {
nodes[i] = new Node;
}
}

template <class T>
bTree<T>::~bTree() {
clear(root);
}

template <class T>
void bTree<T>::clear(Node *p) {
if (p == NULL) {
return;
}

clear(p->left);
clear(p->right);
delete p;
}

template <class T>
void bTree<T>::addNode(int n, int i, T x, bool isRight) {
if (i != 0 && !isRight) {
nodes[i]->parent = nodes[n];
nodes[n]->left = nodes[i];
} else if (i != 0 && isRight) {
nodes[i]->parent = nodes[n];
nodes[n]->right = nodes[i];
}
// nodes[n]->data=x;
}

template <class T>
void bTree<T>::findRoot() {
root = nodes[1];
while (root->parent != NULL) {
root = root->parent;
}
}

template <class T>
void bTree<T>::checkTree(int N, Node *p) {
int count = 0;
bool flag = 0;
seqQueue<Node *> levelNode;
levelNode.enQueue(p);

while (count < N) {
if (!flag && levelNode.getHead()->left == NULL &&
flag = 1;
}

count++;
}

if (count == N) {
break;
}

if (flag && count < N && levelNode.getHead()->parent == NULL &&
cout << "N\n";
return;
}

}

}

levelNode.deQueue();
}
cout << "Y\n";
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int leftNum[maxN + 100], rightNum[maxN + 100], N;

cin >> N;
bTree<int> Tree(N);
for (int i = 1; i <= N; i++) {
cin >> leftNum[i] >> rightNum[i];
}

for (int i = 1; i <= N; i++) {
}

Tree.findRoot();

Tree.checkTree(N, Tree.root);

return 0;
}
``````

## skyzh's solution

``````#include <iostream>
#include <cstdio>
using namespace std;

template <typename T>
struct Queue {
T* d;
int f, r;
Queue(int cap) : d(new T[cap]), f(0), r(0) {}
bool empty() { return f == r; }
void enqueue(const T& x) { d[r++] = x; }
const T dequeue() { return d[f++]; }
~Queue() { delete[] d; }
};

template <typename T>
struct Tree {
T x;
Tree *l, *r;
Tree() : l(NULL), r(NULL) {}
Tree(const T& x, Tree* l = NULL, Tree* r = NULL) : x(x), l(l), r(r) {}
int children_count() const { return (l ? 1 : 0) + (r ? 1 : 0); }
};

Tree <int> nodes[100005];
bool is_child[100005] = { 0 };

int main() {
int N, l, r;
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%d%d", &l, &r);
nodes[i].l = l == 0 ? NULL : &nodes[l];
nodes[i].r = r == 0 ? NULL : &nodes[r];
is_child[l] = is_child[r] = true;
}
int root = 0;
for (int i = 1; i <= N; i++) if (!is_child[i]) root = i;
Queue <Tree <int> *> q(400005);
q.enqueue(&nodes[root]);
int min_children = 2;
bool result = true;
while (!q.empty()) {
Tree <int> *node = q.dequeue();
if (node == NULL) {
min_children = -1;
continue;
}
if (node->children_count() > min_children) result = false;
min_children = min(min_children, node->children_count());
q.enqueue(node->l);
q.enqueue(node->r);
}
if (result) cout << "Y" << endl; else cout << "N" << endl;
return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
#include <cstdio>
using namespace std;
int ls[200000],rs[200000],t[200000],n,d=-1,root;
bool ans=true,sec=true;
void dfs(int i,int depth)
{
if (ls[i]) dfs(ls[i],depth+1);
if ((!ls[i])||(!rs[i])) {
if (d == -1)
d = depth;
else {
if ((depth == d - 1) && sec) {
d = depth;
sec = false;
}
if (d != depth) ans = false;
}
}
if (rs[i]) dfs(rs[i],depth+1);

}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;++i){
scanf("%d%d",&ls[i],&rs[i]);
t[ls[i]]++;
t[rs[i]]++;
}
for (int i=1;i<=n;++i)
if (!t[i]) {
root=i;
break;
}
dfs(root,1);
if (ans) printf("Y");
else printf("N");
return 0;
}
``````

## yyong119's solution

``````#include <cstdio>
#include <queue>
using namespace std;

const int MAX_N = 100000;
struct node_data {
int left_child, right_child, father;
} node[MAX_N + 10];

int main() {

int n; scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int tmp_left, tmp_right; scanf("%d%d", &tmp_left, &tmp_right);
node[i].left_child = tmp_left;
node[tmp_left].father = i;
node[i].right_child = tmp_right;
node[tmp_right].father = i;
}

int root = 1;
while (node[root].father) root = node[root].father;
queue<int> que; que.push(root);
int cnt = 1; bool flag = true;

while (!que.empty()) {
int tmp = que.front(); que.pop();
if (node[tmp].left_child) {
que.push(node[tmp].left_child);
++cnt;
}
else if(cnt < n) {
flag = false; break;
}
if (node[tmp].right_child) {
que.push(node[tmp].right_child);
++cnt;
}
else if (cnt < n) {
flag = false; break;
}
}
if (flag) printf("%c\n", 'Y'); else printf("%c\n", 'N');

return 0;
}
``````