摘要
Title: A1110 Complete Binary Tree
Tag: 完全二叉树
Memory Limit: 64 MB
Time Limit: 1000 ms

A1110 Complete Binary Tree

题意

Given a tree, you are supposed to tell if it is a complete binary tree.
思路

判断是否为完全二叉树
- 思路1：
  - 将所有结点（包括-1）按层序遍历全部加入队列中，开始往外弹，弹到第一个-1停止，继续弹，如果此时出现不是-1的，那么就不是完全二叉树
- 思路2：
  - DFS，从根开始，记录当前点的下标最大值，如果最大值和n相同，则是完全二叉树

代码

思路1

/*
* @Author: NEFU AB-IN
* @Date: 2022-09-13 15:56:41
* @FilePath: \GPLT\A1110\A1110.cpp
* @LastEditTime: 2022-09-13 16:16:45
*/
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> l(n, -1), r(n, -1), st(n);
    for (int i = 0; i < n; ++i)
    {
        string p, q;
        cin >> p >> q;
        if (p != "-")
            l[i] = stoi(p), st[stoi(p)] = 1;
        if (q != "-")
            r[i] = stoi(q), st[stoi(q)] = 1;
    }

    int root;
    for (int i = 0; i < n; ++i)
    {
        if (!st[i])
        {
            root = i;
            break;
        }
    }

    // cout << root << '\n';
    queue<int> ans;
    queue<int> q;
    q.push(root);
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        ans.push(t);
        // cout << t << '\n';
        if (~t)
        {
            q.push(l[t]);
            q.push(r[t]);
        }
    }

    int res;
    while (ans.size())
    {
        if (ans.front() != -1)
        {
            res = ans.front();
            ans.pop();
        }
        else
            break;
    }

    int flag = 1;
    while (ans.size())
    {
        if (~ans.front())
        {
            flag = 0;
            break;
        }
        ans.pop();
    }

    if (flag)
        cout << "YES " << res;
    else
        cout << "NO " << root;
}

思路2

#include <cstring>
#include <iostream>

using namespace std;

const int N = 25;

int n;
int l[N], r[N];
bool has_father[N];
int maxk, maxid;

void dfs(int u, int k)
{
    if (u == -1) return;

    if (k > maxk)
    {
        maxk = k;
        maxid = u;
    }

    dfs(l[u], k * 2);
    dfs(r[u], k * 2 + 1);
}

int main()
{
    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);

    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        string a, b;
        cin >> a >> b;
        if (a != "-") l[i] = stoi(a), has_father[l[i]] = true;
        if (b != "-") r[i] = stoi(b), has_father[r[i]] = true;
    }

    int root = 0;
    while (has_father[root]) root ++ ;

    dfs(root, 1);

    if (maxk == n) printf("YES %d\n", maxid);
    else printf("NO %d\n", root);

    return 0;
}

A1110 Complete Binary Tree

题意

思路

代码