[PAT-A] 1159 Structure of a Binary Tree

Java

import java.util.Scanner;

public class Main {
    static final int N = 1010;

    static int n, m;
    static int[] l = new int[N], r = new int[N], w = new int[N];
    static int[] p = new int[N], depth = new int[N];
    static int[] post = new int[N], in = new int[N], inPos = new int[N];
    static boolean isFull = true;

    static int build(int inL, int inR, int postL, int postR, int d) {
        int root = post[postR];
        depth[root] = d;

        int k = inPos[root];
        int childCnt = 0;
        if (inL < k) {
            l[root] = build(inL, k - 1, postL, postL + (k - 1 - inL), d + 1);
            p[l[root]] = root;
            childCnt++;
        }
        if (k < inR) {
            r[root] = build(k + 1, inR, postL + (k - 1 - inL) + 1, postR - 1, d + 1);
            p[r[root]] = root;
            childCnt++;
        }
        if (childCnt == 1) {
            isFull = false;
        }

        return root;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            post[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            in[i] = scanner.nextInt();
            inPos[in[i]] = i;
        }

        int root = build(0, n - 1, 0, n - 1, 0);
        p[root] = -1;

        m = scanner.nextInt();
        scanner.nextLine();
        String s;
        StringBuilder sb;
        while (m-- > 0) {
            s = scanner.nextLine();
            sb = new StringBuilder();

            boolean flag;
            if (s.charAt(s.length() - 1) == 't') {
                for (int i = 0; i < s.length() && Character.isDigit(s.charAt(i)); i++) {
                    sb.append(s.charAt(i));
                }
                int a = Integer.parseInt(sb.toString());
                flag = (a == root);
            } else if (s.charAt(0) == 'I') {
                flag = isFull;
            } else {
                int a, b, i = 0;
                for (; i < s.length() && Character.isDigit(s.charAt(i)); i++) {
                    sb.append(s.charAt(i));
                }
                a = Integer.parseInt(sb.toString());
                sb = new StringBuilder();
                while (i < s.length() && !Character.isDigit(s.charAt(i))) {
                    i++;
                }
                for (; i < s.length() && Character.isDigit(s.charAt(i)); i++) {
                    sb.append(s.charAt(i));
                }
                b = Integer.parseInt(sb.toString());

                if (s.charAt(s.length() - 1) == 's') {
                    flag = (p[a] == p[b]);
                } else if (s.charAt(s.length() - 1) == 'l') {
                    flag = (depth[a] == depth[b]);
                } else if (s.contains("parent")) {
                    flag = (p[b] == a);
                } else if (s.contains("right")) {
                    flag = (r[b] == a);
                } else {
                    flag = (l[b] == a);
                }
            }

            if (flag) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }

        scanner.close();
    }
}

C++

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int l[N], r[N], w[N];
int p[N], depth[N];
int post[N], in[N], inpos[N];
bool is_full = true;

int build(int inL, int inR, int postL, int postR, int d) {
    // if (inL > inR) return 1009;    // 须为严格大于号，或直接不特判

    int root = post[postR];
    depth[root] = d;

    int k = inpos[root];
    int ccnt = 0;
    if (inL < k) {
        l[root] = build(inL, k - 1, postL, postL + (k - 1 - inL), d + 1);
        p[l[root]] = root;
        ccnt++;
    }
    if (k < inR) {
        r[root] = build(k + 1, inR, postL + (k - 1 - inL) + 1, postR - 1, d + 1);
        p[r[root]] = root;
        ccnt++;
    }
    if (ccnt == 1) is_full = false;

    return root;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &post[i]);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &in[i]);
        inpos[in[i]] = i;
    }

    int root = build(0, n - 1, 0, n - 1, 0);
    p[root] = -1;

    scanf("%d", &m);
    getchar();
    string s, tmp;
    while (m--) {
        getline(cin, s);
        bool flag = false;
        tmp.clear();

        if (s[s.size() - 1] == 't') {    // root
            for (int i = 0; isdigit(s[i]); ++i) tmp += s[i];
            int a = stoi(tmp);
            flag = (a == root);
        } else if (s[0] == 'I') {    // full tree
            flag = is_full;
        } else {
            int a, b, i = 0;
            for (; isdigit(s[i]); ++i) tmp += s[i];
            a = stoi(tmp);
            tmp.clear();
            while (i < s.size() && !isdigit(s[i])) ++i;
            for (; i < s.size() && isdigit(s[i]); ++i) tmp += s[i];
            b = stoi(tmp);

            if (s[s.size() - 1] == 's') flag = (p[a] == p[b]);    // siblings
            else if (s[s.size() - 1] == 'l') flag = (depth[a] == depth[b]); // level
            else if (s.find("parent") < s.size()) flag = (p[b] == a);
            else if (s.find("right") < s.size()) flag = (r[b] == a);
            else flag = (l[b] == a);
        }

        if (flag) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}