11211: 【原1211】isCBT

题目

题目描述

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

Description

给出一棵二叉树的结构,判断这棵二叉树是不是完全二叉树。必须使用二叉树类实现。

Input Format

输入文件一共包含N+1行。

第一行含有一个正整数N，代表树中结点总数。

第二行到第N+1行，每行包含二个整数。其中第i行的二个整数Pi，Qi，代表结点i的左孩子为Pi，右孩子为Qi。若Pi=0，则表明结点i没有左孩子。同样的，若Qi=0，则表明结点i没有右孩子。(第i行指的是这N行中的第i行)

Output Format

如果给出的树是完全二叉树，则输出'Y',否则输出'N'。(均不包含引号)

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

Limit

对于所有的数据，均满足1<=N<=100000

对于所有的数据，均满足0<=Pi,Qi<=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;
        binaryTree.add(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;
    };
    node* head = nullptr,
        * rear = nullptr;
    size_t _size = 0;

public:
    //构造函数
    mQueue() {
        head = new node;
        rear = head;
    }
    //判断是否为空
    bool empty() {
        return head->next == nullptr;
    }
    //增加
    void push(const T& val) {
        rear->next = new node;
        rear = rear->next;
        rear->data = val;
        ++_size;
    }
    //删除
    void pop() {
        //安全措施
        if (head->next == nullptr)
            return;
        auto temp = head->next;
        delete head;
        head = temp;
        --_size;
    }
    //大小
    size_t size() {
        return _size;
    }
    //最前
    T& front() {
        //安全措施
        return head->next->data;
    }
    //最后
    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.creadNode(i, 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();
    elemType getHead() const;
    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>
elemType seqQueue<elemType>::getHead() const {
    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 addNode(int, int, T, bool);
    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 &&
            levelNode.getHead()->right == NULL) {
            flag = 1;
        }

        if (levelNode.getHead()->parent != NULL ||
            levelNode.getHead() == root) {
            count++;
        }

        if (count == N) {
            break;
        }

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

        if (levelNode.getHead()->left == NULL) {
            levelNode.getHead()->left = new Node;
        }

        if (levelNode.getHead()->right == NULL) {
            levelNode.getHead()->right = new Node;
        }

        levelNode.enQueue(levelNode.getHead()->left);
        levelNode.enQueue(levelNode.getHead()->right);
        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.addNode(i, leftNum[i], 0, 0);
        Tree.addNode(i, rightNum[i], 0, 1);
    }

    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;
}