PAT 1110. 完全二叉树
原题链接
简单
作者:
YAX_AC
,
2024-11-15 21:52:46
,
所有人可见
,
阅读 6
//complete binary tree完全二叉树 indices指标指数
//For each case, print in one line YES and the index of the last node if the tree is a complete binary tree
//对于每种情况,如果树是完整的二叉树,请在一行中打印“是”和最后一个节点的索引
//or NO and the index of the root if not.
//否则打印“否”和根的索引
//Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node.
//接下来是N行,每行对应一个节点,并给出节点左右子节点的索引。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 25;
int n;
int l[N],r[N];
bool has_father[N];//记录每个点是否有父节点,没有父节点的即为根节点
int maxk,lastid;
void dfs(int root, int k)
{
if(maxk < k)
{
lastid = root;
maxk = k;
}
if(l[root] != -1) dfs(l[root], 2 * k); //左孩子
if(r[root] != -1) dfs(r[root], 2 * k + 1); //右孩子
}
int main()
{
cin>>n;
memset(l,-1,sizeof l);
memset(r,-1,sizeof r);
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;
while(has_father[root]) root++;
dfs(root, 1);
if(maxk > n) cout << "NO " << root << endl;
else cout << "YES " << lastid << endl;
}