【題解】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
分享本文 Share with friends