判断完全二叉树

题设

问题描述

假设二叉树中的每个结点值为单个整数，采用二叉链结构存储，设计算法判断给定的二叉树是否是完全二叉树。假定每棵二叉树节点不超过2000个。

输入形式

每个测试是一颗二叉树的括号表示法字符串

输出形式

如果是完全二叉树，输出“1”；如果不是完全二叉树，输出“0”

样例输入

1(2(4,5),3)

样例输出

1

题解

先建树，这里依然是用的l数组和r数组。建完树之后用BFS判断是否是完全二叉树，方法是当出现子树为空时，记录一下，若之后出现非空子树，那么一定是非完全二叉树

#include <iostream>
using namespace std;
const int N = 100010;

int l[N], r[N], e[N], q[N], root, idx;
char line[N];

int pars(char *&s) {
  if (*s == '\0' || !isdigit(*s)) return 0;

  int u = ++idx;
  int val = 0;
  while (isdigit(*s)) {
    val = val * 10 + (*s - '0');
    s++;
  }
  e[idx] = val;
  if (*s == '(') {
    s++;
    l[u] = pars(s);
    if (*s == ',') {
      s++;
      r[u] = pars(s);
    }
    if (*s == ')') {
      s++;
    }
  }

  return u;
}

bool check_complete(int root) {
  if (!root) return true;
  int hh = 0, tt = 0;
  q[0] = root;
  bool flag = false;
  while (hh <= tt) {
    int t = q[hh++];
    if (l[t]) {
      if (flag) return false;
      q[++tt] = l[t];
    } else
      flag = true;
    if (r[t]) {
      if (flag) return false;
      q[++tt] = r[t];
    } else
      flag = true;
  }
  return true;
}

int main() {
  // freopen("in.txt", "r", stdin);
  scanf("%s", line);
  char *input = line;
  root = pars(input);
  if (check_complete(root))
    puts("1");
  else
    puts("0");
  return 0;
}