完全二叉树

• 如果按照其层序遍历放到 1~n 下标的点中去，那么 x * 2 是 x 的左结点， x * 2 + 1 是 x 的右结点。

• std::stoi 用来将字符串转换为 int 。这里的字符串指的是 string 。

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 26;

int n, l[N], r[N];
bool has_father[N];
int root = -1;
int maxk = -1;
int maxid = -1;

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 != "-") 
      {
          int pos = stoi(a);
          l[i] = pos;
          has_father[pos] = true;
      }
      if (b != "-")
      {
          int pos = stoi(b);
          r[i] = pos;
          has_father[pos] = true;
      }
  }

  while (has_father[ ++ root]);

  // k表示如果在一颗完全二叉树里面的话这个点的下标
  int k = 1;
  dfs(root, k);

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

  return 0;
}