PAT Spring Examination 2019 7-4 Structure of a Binary Tree (30)

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, a binary tree can be uniquely determined.
Now given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statment is one of the following:

  • A is the root
  • A and B are siblings
  • A is the parent of B
  • A is the left child of B
  • A is the right child of B
  • A and B are on the same level
  • It is a full tree

Note:

  • Two nodes are on the same level, means that they have the same depth.
  • A full binary tree is a tree in which every node other than the leaves has two children.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer NNN (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are no more than 103 and are separated by a space.
Then another positive integer MMM (≤30) is given, followed by MMM lines of statements. It is guaranteed that both A and B in the statements are in the tree.

Output Specification:

For each statement, print in a line Yes if it is correct, or No if not.

Sample Input:

9
16 7 11 32 28 2 23 8 15
16 23 7 32 11 2 28 15 8
7
15 is the root
8 and 2 are siblings
32 is the parent of 11
23 is the left child of 16
28 is the right child of 2
7 and 11 are on the same level
It is a full tree

Sample Output:

Yes
No
Yes
No
Yes
Yes
Yes

meaning of the title

Give the traversal of the middle and post-order of the binary tree, and judge whether the proposition of this number is correct or not.

thinking

This question is simpler than Question 3. They should change their order.
In order to judge the proposition related to depth and parent node, it is better to add depth information and parent node pointer to the node.

Code

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

struct node {
    int val, depth;
    node *lChild = nullptr, *rChild = nullptr, *parent = nullptr;
};

int postOrder[35], inOrder[35];
bool isFull = true;

node *create(int postRoot, int inL, int inR, int depth, node *parent) {
    if (inL > inR) return nullptr;

    node *root = new node;
    root->depth = depth;
    root->parent = parent;
    root->val = postOrder[postRoot];

    int inRoot = inL;
    while (inOrder[inRoot] != postOrder[postRoot]) ++inRoot;

    root->lChild = create(postRoot - 1 - inR + inRoot, inL, inRoot - 1, depth + 1, root);
    root->rChild = create(postRoot - 1, inRoot + 1, inR, depth + 1, root);

    if ((root->lChild == nullptr && root->rChild != nullptr) ||
        (root->lChild != nullptr && root->rChild == nullptr))
        isFull = false;

    return root;
}

node *dfs(node *root, int target) {
    if (root == nullptr || root->val == target) return root;
    node *ret = dfs(root->lChild, target);
    if (ret && ret->val == target) return ret;
    return dfs(root->rChild, target);
}

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);

    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i)
        cin >> postOrder[i];
    for (int i = 0; i < n; ++i)
        cin >> inOrder[i];

    node *root = create(n - 1, 0, n - 1, 0, nullptr);

    cin >> n;
    cin.get();
    for (int i = 0; i < n; ++i) {
        bool ok;
        string s;
        int a, b;
        getline(cin, s);

        if (*s.rbegin() == 't') {
            sscanf(s.c_str(), "%d", &a);
            ok = a == root->val;
        } else if (*s.rbegin() == 'e') {
            ok = isFull;
        } else if (*s.rbegin() == 's') {
            sscanf(s.c_str(), "%d and %d", &a, &b);
            node *ra = dfs(root, a);
            node *rb = dfs(root, b);
            ok = ra && rb && ra->parent == rb->parent;
        } else if (*s.rbegin() == 'l') {
            sscanf(s.c_str(), "%d and %d", &a, &b);
            node *ra = dfs(root, a);
            node *rb = dfs(root, b);
            ok = ra && rb && ra->depth == rb->depth;
        } else if (s.find("parent") != string::npos) {
            sscanf(s.c_str(), "%d is the parent of %d", &a, &b);
            node *ra = dfs(root, a);
            ok = ra && ((ra->lChild && ra->lChild->val == b) ||
                        (ra->rChild && ra->rChild->val == b));
        } else if (s.find("left") != string::npos) {
            sscanf(s.c_str(), "%d is the left child of %d", &a, &b);
            node *rb = dfs(root, b);
            ok = rb && rb->lChild && rb->lChild->val == a;
        } else {
            sscanf(s.c_str(), "%d is the right child of %d", &a, &b);
            node *rb = dfs(root, b);
            ok = rb && rb->rChild && rb->rChild->val == a;
        }
        cout << (ok ? "Yes\n" : "No\n");
    }
}

Tags: iOS

Posted on Mon, 07 Oct 2019 17:05:19 -0700 by LuaMadman