PAT – 第31页

1099. Build A Binary Search Tree (30)-PAT甲级真题

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.
Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format “left_index right_index”, provided that the nodes are numbered from 0 to N-1, and 0 is always the root. If one child is missing, then -1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.

Output Specification:

For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.

Sample Input:
9
1 6
2 3
-1 -1
-1 4
5 -1
-1 -1
7 -1
-1 8
-1 -1
73 45 11 58 82 25 67 38 42
Sample Output:
58 25 82 11 38 67 45 73 42

题目大意：给出一棵二叉搜索树（给出每个结点的左右孩子），且已知根结点为0，求并且给出应该插入这个二叉搜索树的数值，求这棵二叉树的层序遍历
分析：1. 用结构体data，left，right表示这棵树的结构，a数组存树的信息，b数组存这棵树节点的所有data，根据输入可知树a[i]的left和right～
2. 因为是二叉搜索树，所以中序遍历这棵树得到的结点顺序应该是给出的数值序列从小到大的排列顺序，所以把数值序列排序后，可以在中序遍历的时候直接赋值当前a[root].data～同时可得知树的最大层数maxLevel的值～
3. 二维数组v用来存储每一层的结点下标，一共有0到maxLevel层。用for循环从0开始一层层遍历v，就可以得到下一层的l和r，遍历过程中可以输出每个结点对应的data值a[v[i][j]].data～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, cnt, b[100], maxLevel;
struct node {
    int data, l, r;
}a[110];
vector<int> v[100];
void dfs(int root, int level) {
    maxLevel = max(level, maxLevel);
    if (a[root].l != -1) dfs(a[root].l, level + 1);
    a[root] = {b[cnt++], a[root].l, a[root].r};
    if (a[root].r != -1) dfs(a[root].r, level + 1);
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i].l >> a[i].r;
    for (int i = 0; i < n; i++) cin >> b[i];
    sort(b, b + n);
    dfs(0, 0);
    v[0].push_back(0);
    for (int i = 0; i <= maxLevel; i++) {
        for (int j = 0; j < v[i].size(); j++) {
            if (i != 0) cout << " ";
            cout << a[v[i][j]].data;
            if(a[v[i][j]].l != -1) v[i+1].push_back(a[v[i][j]].l);
            if(a[v[i][j]].r != -1) v[i+1].push_back(a[v[i][j]].r);
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int n, cnt, b[100], maxLevel;

struct node {

int data, l, r;

}a[110];

vector<int> v[100];

void dfs(int root, int level) {

maxLevel = max(level, maxLevel);

if (a[root].l != -1) dfs(a[root].l, level + 1);

a[root] = {b[cnt++], a[root].l, a[root].r};

if (a[root].r != -1) dfs(a[root].r, level + 1);

}

int main() {

cin >> n;

for (int i = 0; i < n; i++) cin >> a[i].l >> a[i].r;

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

sort(b, b + n);

dfs(0, 0);

v[0].push_back(0);

for (int i = 0; i <= maxLevel; i++) {

for (int j = 0; j < v[i].size(); j++) {

if (i != 0) cout << " ";

cout << a[v[i][j]].data;

if(a[v[i][j]].l != -1) v[i+1].push_back(a[v[i][j]].l);

if(a[v[i][j]].r != -1) v[i+1].push_back(a[v[i][j]].r);

}

return 0;

}

1086. Tree Traversals Again (25)-PAT甲级真题（树的遍历，前序中序转后序）

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.

Output Specification:

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
Sample Output:
3 4 2 6 5 1
题目大意：用栈的形式给出一棵二叉树的建立的顺序，求这棵二叉树的后序遍历
分析：栈实现的是二叉树的中序遍历（左根右），而每次push入值的顺序是二叉树的前序遍历（根左右），所以该题可以用二叉树前序和中序转后序的方法做～
root为当前子树的根结点在前序pre中的下标，start和end为当前子树的最左边和最右边的结点在中序in中的下标。用i找到当前子树的根结点root在中序中的下标，然后左边和右边就分别为当前根结点root的左子树和右子树。递归实现～
Update：Github用户littlesevenmo给我发issue提出题目并没有说所有节点的值互不相同。因此，在有多个节点的值相同的情况下，之前的代码会输出错误的结果，所以修改后的代码中添加了key作为索引，前中后序中均保存索引值，然后用value存储具体的值，修改后的代码如下：

#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
vector<int> pre, in, post,value;
void postorder(int root, int start, int end) {
    if (start > end) return;
    int i = start;
    while (i < end && in[i] != pre[root]) i++;
    postorder(root + 1, start, i - 1);
    postorder(root + 1 + i - start, i + 1, end);
    post.push_back(pre[root]);
}
int main() {
    int n;
    scanf("%d", &n);
    char str[5];
    stack<int> s;
    int key=0;
    while (~scanf("%s", str)) {
        if (strlen(str) == 4) {
            int num;
            scanf("%d", &num);
            value.push_back(num);
            pre.push_back(key);
            s.push(key++);
        } else {
            in.push_back(s.top());
            s.pop();
        }
    }
    postorder(0, 0, n - 1);
    printf("%d", value[post[0]]);
    for (int i = 1; i < n; i++)
        printf(" %d",value[post[i]]);
    return 0;
}

#include <cstdio>

#include <vector>

#include <stack>

#include <cstring>

using namespace std;

vector<int> pre, in, post,value;

void postorder(int root, int start, int end) {

if (start > end) return;

int i = start;

while (i < end && in[i] != pre[root]) i++;

postorder(root + 1, start, i - 1);

postorder(root + 1 + i - start, i + 1, end);

post.push_back(pre[root]);

}

int main() {

int n;

scanf("%d", &n);

char str[5];

stack<int> s;

int key=0;

while (~scanf("%s", str)) {

if (strlen(str) == 4) {

int num;

scanf("%d", &num);

value.push_back(num);

pre.push_back(key);

s.push(key++);

} else {

in.push_back(s.top());

s.pop();

}

postorder(0, 0, n - 1);

printf("%d", value[post[0]]);

for (int i = 1; i < n; i++)

printf(" %d",value[post[i]]);

return 0;

}

1102. Invert a Binary Tree (25)-PAT甲级真题

The following is from Max Howell @twitter:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
Now it’s your turn to prove that YOU CAN invert a binary tree!

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=10) which is the total number of nodes in the tree — and hence the nodes are numbered from 0 to N-1. Then N lines follow, each corresponds to a node from 0 to N-1, and gives the indices of the left and right children of the node. If the child does not exist, a “-” will be put at the position. Any pair of children are separated by a space.

Output Specification:

For each test case, print in the first line the level-order, and then in the second line the in-order traversal sequences of the inverted tree. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

Sample Input:
8
1 –
– –
0 –
2 7
– –
– –
5 –
4 6
Sample Output:
3 7 2 6 4 0 5 1
6 5 7 4 3 2 0 1
题目大意：反转一棵二叉树，给出原二叉树的每个结点的左右孩子，输出它的层序和中序遍历～

分析：1. 反转二叉树就是存储的时候所有左右结点都交换。
2. 二叉树使用{id, l, r, index, level}存储每个结点的id, 左右结点,下标值，和当前层数～
3. 根结点是所有左右结点中没有出现的那个结点～
4. 已知根结点，用递归的方法可以把中序遍历的结果push_back到数组v1里面，直接输出就是中序，排序输出就是层序（排序方式，层数小的排前面，相同层数时，index大的排前面）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    int id, l, r, index, level;
} a[100];
vector<node> v1;
void dfs(int root, int index, int level) {
    if (a[root].r != -1) dfs(a[root].r, index * 2 + 2, level + 1);
    v1.push_back({root, 0, 0, index, level});
    if (a[root].l != -1) dfs(a[root].l, index * 2 + 1, level + 1);
}
bool cmp(node a, node b) {
    if (a.level != b.level) return a.level < b.level;
    return a.index > b.index;
}
int main() {
    int n, have[100] = {0}, root = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        a[i].id = i;
        string l, r;
        cin >> l >> r;
        if (l != "-") {
            a[i].l = stoi(l);
            have[stoi(l)] = 1;
        } else {
            a[i].l = -1;
        }
        if (r != "-") {
            a[i].r = stoi(r);
            have[stoi(r)] = 1;
        } else {
            a[i].r = -1;
        }
    }
    while (have[root] == 1) root++;
    dfs(root, 0, 0);
    vector<node> v2(v1);
    sort(v2.begin(), v2.end(), cmp);
    for (int i = 0; i < v2.size(); i++) {
        if (i != 0) cout << " ";
        cout << v2[i].id;
    }
    cout << endl;
    for (int i = 0; i < v1.size(); i++) {
        if (i != 0) cout << " ";
        cout << v1[i].id;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct node {

int id, l, r, index, level;

} a[100];

vector<node> v1;

void dfs(int root, int index, int level) {

if (a[root].r != -1) dfs(a[root].r, index * 2 + 2, level + 1);

v1.push_back({root, 0, 0, index, level});

if (a[root].l != -1) dfs(a[root].l, index * 2 + 1, level + 1);

}

bool cmp(node a, node b) {

if (a.level != b.level) return a.level < b.level;

return a.index > b.index;

}

int main() {

int n, have[100] = {0}, root = 0;

cin >> n;

for (int i = 0; i < n; i++) {

a[i].id = i;

string l, r;

cin >> l >> r;

if (l != "-") {

a[i].l = stoi(l);

have[stoi(l)] = 1;

} else {

a[i].l = -1;

}

if (r != "-") {

a[i].r = stoi(r);

have[stoi(r)] = 1;

} else {

a[i].r = -1;

}

while (have[root] == 1) root++;

dfs(root, 0, 0);

vector<node> v2(v1);

sort(v2.begin(), v2.end(), cmp);

for (int i = 0; i < v2.size(); i++) {

if (i != 0) cout << " ";

cout << v2[i].id;

}

cout << endl;

for (int i = 0; i < v1.size(); i++) {

if (i != 0) cout << " ";

cout << v1[i].id;

}

return 0;

}

L3-010. 是否完全二叉搜索树-PAT团体程序设计天梯赛GPLT

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。

输入格式：

输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。

输出格式：

将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出“YES”，如果该树是完全二叉树；否则输出“NO”。

输入样例1：
9
38 45 42 24 58 30 67 12 51
输出样例1：
38 45 24 58 42 30 12 67 51
YES
输入样例2：
8
38 24 12 45 58 67 42 51
输出样例2：
38 45 24 58 42 12 67 51
NO
分析：根据二叉树的性质，i结点的左孩子为root<<1，右孩子为root<<1|1.建造并用数组存储这个二叉搜索树，然后判断是否是完全二叉树。

#include <cstdio>
using namespace std;
int tree[1<<20];
int num;
void BST(int a) {
    if(tree[a] == 0)
        tree[a] = num;
    else if(tree[a] < num)
        BST(a<<1);
    else
        BST(a<<1|1);
}
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &num);
        BST(1);
    }
    bool flag = true;
        for(int cnt = 1, k = 1; cnt <= n; k++) {
            if(tree[k] == 0)
                flag = false;
            else {
                printf("%d", tree[k]);
                if(cnt++ != n) printf(" ");
            }
        }
    if(flag) printf("\nYES");
    else printf("\nNO");
    return 0;
}

#include <cstdio>

using namespace std;

int tree[1<<20];

int num;

void BST(int a) {

if(tree[a] == 0)

tree[a] = num;

else if(tree[a] < num)

BST(a<<1);

else

BST(a<<1|1);

}

int main() {

int n;

scanf("%d", &n);

for(int i = 0; i < n; i++) {

scanf("%d", &num);

BST(1);

}

bool flag = true;

for(int cnt = 1, k = 1; cnt <= n; k++) {

if(tree[k] == 0)

flag = false;

else {

printf("%d", tree[k]);

if(cnt++ != n) printf(" ");

}

if(flag) printf("\nYES");

else printf("\nNO");

return 0;

}

1064. Complete Binary Search Tree (30)-PAT甲级真题（树的层序遍历）

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input:
10
1 2 3 4 5 6 7 8 9 0
Sample Output:
6 3 8 1 5 7 9 0 2 4
题目大意：给一串构成树的序列，已知该树是完全二叉搜索树，求它的层序遍历的序列
分析：总得概括来说，已知中序，从根节点开始中序遍历，按中序数组给出的顺序依次将值填入level数组对应的下标中，输出level数组可得层序遍历。
1. 因为二叉搜索树的中序满足：是一组序列的从小到大排列，所以只需将所给序列排序即可得到中序数组in
2. 假设把树按从左到右、从上到下的顺序依次编号，根节点为0，则从根结点root = 0开始中序遍历，root结点的左孩子下标是root*2+1，右孩子下标是root*2+2
3. 因为是中序遍历，所以遍历结果与中序数组in中的值从0开始依次递增的结果相同，即in[t++]（t从0开始），将in[t++]赋值给level[root]数组
4. 因为树是按从左到右、从上到下的顺序依次编号的，所以level数组从0到n-1的值即所求的层序遍历的值，输出level数组即可～

#include <iostream>
#include <algorithm>
using namespace std;
int in[1010], level[1010], n, t = 0;
void inOrder(int root) {
    if (root >= n) return ;
    inOrder(root * 2 + 1);
    level[root] = in[t++];
    inOrder(root * 2 + 2);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &in[i]);
    sort(in, in + n);
    inOrder(0);
    printf("%d", level[0]);
    for (int i = 1; i < n; i++)
        printf(" %d", level[i]);
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int in[1010], level[1010], n, t = 0;

void inOrder(int root) {

if (root >= n) return ;

inOrder(root * 2 + 1);

level[root] = in[t++];

inOrder(root * 2 + 2);

}

int main() {

scanf("%d", &n);

for (int i = 0; i < n; i++)

scanf("%d", &in[i]);

sort(in, in + n);

inOrder(0);

printf("%d", level[0]);

for (int i = 1; i < n; i++)

printf(" %d", level[i]);

return 0;

}

1110. Complete Binary Tree (25)-PAT甲级真题（BFS）

Given a tree, you are supposed to tell if it is a complete binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=20) which is the total number of nodes in the tree — and hence the nodes are numbered from 0 to N-1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a “-” will be put at the position. Any pair of children are separated by a space.

Output Specification:

For each case, print in one line “YES” and the index of the last node if the tree is a complete binary tree, or “NO” and the index of the root if not. There must be exactly one space separating the word and the number.

Sample Input 1:
9
7 8
– –
– –
– –
0 1
2 3
4 5
– –
– –
Sample Output 1:
YES 8
Sample Input 2:
8
– –
4 5
0 6
– –
2 3
– 7
– –
– –
Sample Output 2:
NO 1

题目大意：给出一个n表示有n个结点，这n个结点为0~n-1，给出这n个结点的左右孩子，求问这棵树是不是完全二叉树
分析：递归出最大的下标值，完全二叉树一定把前面的下标充满：最大的下标值 == 最大的节点数；不完全二叉树前满一定有位置是空，会往后挤：最大的下标值 > 最大的节点数～

#include <iostream>
using namespace std;
struct node{
    int l, r;
}a[100];
int maxn = -1, ans;
void dfs(int root, int index) {
    if(index > maxn) {
        maxn = index;
        ans = root;
    }
    if(a[root].l != -1) dfs(a[root].l, index * 2);
    if(a[root].r != -1) dfs(a[root].r, index * 2 + 1);
}
int main() {
    int n, root = 0, have[100] = {0};
    cin >> n;
    for (int i = 0; i < n; i++) {
        string l, r;
        cin >> l >> r;
        if (l == "-") {
            a[i].l = -1;
        } else {
            a[i].l = stoi(l);
            have[stoi(l)] = 1;
        }
        if (r == "-") {
            a[i].r = -1;
        } else {
            a[i].r = stoi(r);
            have[stoi(r)] = 1;
        }
    }
    while (have[root] != 0) root++;
    dfs(root, 1);
    if (maxn == n)
        cout << "YES " << ans;
    else
        cout << "NO " << root;
    return 0;
}

#include <iostream>

using namespace std;

struct node{

int l, r;

}a[100];

int maxn = -1, ans;

void dfs(int root, int index) {

if(index > maxn) {

maxn = index;

ans = root;

}

if(a[root].l != -1) dfs(a[root].l, index * 2);

if(a[root].r != -1) dfs(a[root].r, index * 2 + 1);

}

int main() {

int n, root = 0, have[100] = {0};

cin >> n;

for (int i = 0; i < n; i++) {

string l, r;

cin >> l >> r;

if (l == "-") {

a[i].l = -1;

} else {

a[i].l = stoi(l);

have[stoi(l)] = 1;

}

if (r == "-") {

a[i].r = -1;

} else {

a[i].r = stoi(r);

have[stoi(r)] = 1;

}

while (have[root] != 0) root++;

dfs(root, 1);

if (maxn == n)

cout << "YES " << ans;

else

cout << "NO " << root;

return 0;

}