PAT 甲级 刷题日记|A 1110 Complete Bina

思路

这道题考察完全二叉树的建立及判定 与1123的一部分非常相似，判断思路就是，层次遍历，在空节点右侧，有没有出现其他非空节点。

柳神的代码更加简洁和巧妙，其思想是利用完全二叉树的存储编号特点， 若最大的索引等于给定的节点个数，那么这是一棵完全二叉树，输出"YES"和最后一个节点的索引即可，反之输出"NO"和这棵树的根节点。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 23;
struct node {
    int lchild, rchild;
}Node[maxn];
int flag[maxn];
int n, root, cur;
int ff, no; 

void level(int root) {
    queue<int> mq;
    mq.push(root);
    while (!mq.empty()) {
        cur = mq.front();
        mq.pop();
        if (Node[cur].lchild != -1) {
            mq.push(Node[cur].lchild);
            if (ff == 1) no = 1;
        }
        else if (ff == 0) ff = 1;
        if (Node[cur].rchild != -1) {
            mq.push(Node[cur].rchild);
            if (ff == 1) no = 1;
        }
        else if (ff == 0) ff = 1;
    }
}

int main() {
    cin>>n;
    string s1, s2;
    for (int i = 0; i < n; i++) {
        cin>>s1>>s2;
        if (s1 == "-") Node[i].lchild = -1;
        else {
            Node[i].lchild = stoi(s1);
            flag[stoi(s1)] = 1;
        }
        if (s2 == "-") Node[i].rchild = -1;
        else {
            Node[i].rchild = stoi(s2);
            flag[stoi(s2)] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        if (flag[i] == 0) {
            root = i;
            break;
        }
    }
    level(root);
    if (no == 1) cout<<"NO "<<root<<endl;
    else cout<<"YES "<<cur<<endl;
}

代码2（性质）

#include <bits/stdc++.h>
using namespace std;

const int maxn = 23;
struct node {
    int lchild, rchild;
}Node[maxn];
int flag[maxn];
int n, root;
int maxu = -1, maxindex;


void dfs(int u, int inde) {
    if (inde > maxindex) {
        maxindex = inde;
        maxu = u;
    }
    if (Node[u].lchild != -1) dfs(Node[u].lchild, inde * 2);
    if (Node[u].rchild != -1) dfs(Node[u].rchild, inde * 2 + 1);
}

int main() {
    cin>>n;
    string s1, s2;
    for (int i = 0; i < n; i++) {
        cin>>s1>>s2;
        if (s1 == "-") Node[i].lchild = -1;
        else {
            Node[i].lchild = stoi(s1);
            flag[stoi(s1)] = 1;
        }
        if (s2 == "-") Node[i].rchild = -1;
        else {
            Node[i].rchild = stoi(s2);
            flag[stoi(s2)] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        if (flag[i] == 0) {
            root = i;
            break;
        }
    }
    dfs(root, 1);
    if (maxindex != n) {
        cout<<maxindex<<" NO "<<root<<endl;
    }
    else cout<<"YES "<<maxu<<endl;
}