Post

判断完全二叉树

判断完全二叉树

题设

问题描述

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

输入形式

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

输出形式

如果是完全二叉树,输出“1”;如果不是完全二叉树,输出“0”

样例输入

1
1(2(4,5),3)

样例输出

1
1

题解

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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;
}
This post is licensed under CC BY 4.0 by the author.