# 【題解】ZeroJudge c101: 00122 – Trees on the level

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c101
【解題想法】二元樹實作

#### 【方法1】三個陣列分別存節點值、左兒子、右兒子

```#include <iostream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;

int l, i_val[260], i_ri[260], i_li[260], idx, val, pre, now;
string s, p;
bool flag;

int main() {
while (cin >> s){
if (s.length() == 2) continue;
idx = 2;
flag = true;
memset(i_val, -1, sizeof(i_val));
memset(i_ri, -1, sizeof(i_ri));
memset(i_li, -1, sizeof(i_li));
i_val[1] = 0;
while (1){
val = 0;
l = s.length();
for (int i = 1; i < l-1; i++){
if (s[i] == ','){
if (i == l-2) p = "";
else p = s.substr(i+1, l-i-2);
break;
}
else {
val *= 10;
val += s[i]-'0';
}
}
l = p.length();
if (l == 0) i_val[1] = val;
else{
now = 1;
for (int i = 0; i < l-1; i++){
if (p[i] == 'R'){
if (i_ri[now] == -1){
i_ri[now] = idx;
i_val[idx] = 0;
idx++;
}
now = i_ri[now];
}
else {
if (i_li[now] == -1){
i_li[now] = idx;
i_val[idx] = 0;
idx++;
}
now = i_li[now];
}
}
if (p[l-1] == 'R'){
if (i_ri[now] != -1){
now = i_ri[now];
if (i_val[now] > 0) flag = false;
else i_val[now] = val;
}
else {
i_ri[now] = idx;
i_val[idx] = val;
idx++;
}
}
else {
if (i_li[now] != -1){
now = i_li[now];
if (i_val[now] > 0) flag = false;
else i_val[now] = val;
}
else {
i_li[now] = idx;
i_val[idx] = val;
idx++;
}
}
}
cin >> s;
if (s.length() == 2) break;
}
for (int i = 1; i < idx; i++){
if (i_val[i] == 0){
flag = false;
break;
}
}
if (!flag){
cout << "not complete\n";
continue;
}
cout << i_val[1];
queue <int> q;
q.push(1);
while (!q.empty()){
now = q.front();
q.pop();
if (i_li[now] != -1){
cout << " " << i_val[i_li[now]];
q.push(i_li[now]);
}
if (i_ri[now] != -1){
cout << " " << i_val[i_ri[now]];
q.push(i_ri[now]);
}
}
cout << "\n";
}
}
```

#### 【方法2】一個陣列存二元樹

• C++ code (credit: Amy Chou)
• 換個寫法，用陣列存二元樹
• a[1] = root, a[1*2] = root’s left child, a[1*2 + 1] = root’s right child
• 題目沒有保證是平衡的二元樹，a[256]不夠用，經實測，a[1<<15] 才夠。
```#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int a[1<<15], total;
vector <int> ans;
bool flag;

void solve(){
ans.clear();
if (a[1] == 0) return; //沒有根節點
queue <int> q;
ans.push_back(a[1]);
q.push(1);
while (!q.empty()) {
int now = q.front(); q.pop();
int left = now * 2;
int right = now * 2 + 1;
//按「階層」走訪
if (a[left]){
ans.push_back(a[left]);
q.push(left);
}
if (a[right]){
ans.push_back(a[right]);
q.push(right);
}
}
}

int main() {
string s;
flag = true;
while (cin >> s){
if (s == "()"){
if (flag) solve();
if (flag && ans.size() == total){
bool first = true;
for (auto i: ans){
if (first) first = false;
else cout << " ";
cout << i;
}
cout << "\n";
} else {
cout << "not complete\n";
}
//初始化
memset(a, 0, sizeof(a));
flag = true;
total = 0;
} else {
total++;
int idx = 0;
int i;
for (i = 1; s[i] != ','; i++){
idx *= 10;
idx += s[i] - '0';
}
int pos = 1;
for (i++; i < s.size()-1; i++){
if (s[i] == 'L') pos *= 2;
else pos = pos * 2 + 1;
}
if (a[pos]) flag = false; //同一路徑有2個節點
else a[pos] = idx;
}
}
return 0;
}
```

#### 【方法2 的 Python code】

Python code (credit: Amy Chou)

```def solve():
if a[1] == 0:
return
q = [1]
ans.append(a[1])
while q:
now = q.pop(0)
left = now * 2
right = now * 2 + 1
if a[left]:
ans.append(a[left])
q.append(left)
if a[right]:
ans.append(a[right])
q.append(right)

# main program
while True:
try:
total = 0
a = [0 for _ in range(1<<15)]
end = False
flag = True
ans = []
while True:
S = input().split()
for s in S:
if s == "()":
end = True
break
total += 1
idx = int(s[1:-1].split(',')[0])
pos = 1
for c in s[1:-1].split(',')[1]:
if c == 'L':
pos = pos * 2
else:
pos = pos * 2 + 1

if a[pos]:
flag = False
else:
a[pos] = idx
if end:
break

if flag:
solve()
if len(ans) == total:
first = True
for i in ans:
if first:
first = False
else:
print(' ', end='')
print(i, end='')
print()
else:
print("not complete")
else:
print("not complete")
except:
break
```