解题思路
树的存储
树的每个结点的权各不相同, 且1 <= weight <=1000, 所以我们可以考虑用大数组构建哈希来存储, 数组的下标即是结点的权又是结点的位置, 这样我们就不用额外保存权了
另外为了后续的判断方便, 我们可以对每个结点的前驱进行保存
#define MaxNum 1001
int l[MaxNum], r[MaxNum], pre[MaxNum];//左孩子, 右孩子, 以及前驱(父母)
int Root;//用来保存根结点的位置
以及用两个数组来保存中序和后序序列
int inorder[31], postorder[31];
树的构建
后序是: 左 -> 右 -> 根
中序是: 左 -> 根 -> 右
所以一段后序序列的最后一个元素必然是根结点,
这时候我们可以在中序序列中查找到根的位置i, 这时左右子树的中序序列就确定了:在i左边的是左子树, i右边的是右子树
再通过左右子树的中序序列长度, 我们也可以获取到它们的后序序列.
这样左右子树的中、后序序列我们就都确定了, 进行递归即可
//参数分别为: 中序序列的两个边界, 后序序列的两个边界
int BuildTree(int li, int ri, int lp, int rp){
if(li > ri){
return 0;//0为无效位置
}
int root = postorder[rp];
int i;
for(i=li; i<=ri; i++){
if(inorder[i] == root){
break;
}
}
//边界的确定有些麻烦,检验的一个方法是,两个序列的长度必须相等
l[root] = BuildTree(li, i-1, lp, lp+i-li-1);
if(l[root] != 0){
pre[l[root]] = root;
}
r[root] = BuildTree(i+1, ri, rp+i-ri, rp-1);
if(r[root] != 0){
pre[r[root]] = root;
}
return root;
}
陈述正确性判断
我们先把陈述读入字符串内, 然后对字符串中查找关键字以确定陈述的类型, 用sscanf读入数据, 进行判断即可
在给出完整函数之前, 我们先来解决一些比较难判断的陈述
- 结点的层次
我们用一个数组来保存所有结点的层次信息, 再用一个函数完成层次信息的获取
int Level[MaxNum];
void getLevel(int root, int level){
if(root == 0){
return;
}
Level[root] = level;
getLevel(l[root], level+1);
getLevel(r[root], level+1);
}
- 是否为满二叉树
满二叉树即除叶结点外所有的结点的度都为2
给出判断函数
bool IsFullTree(int root){
if((r[root] == 0) && (l[root] == 0)){//叶子结点
return true;
}
if((r[root] == 0) ^ (l[root] == 0)){//度为1的结点
return false;
}
return IsFullTree(l[root]) && IsFullTree(r[root]);
}
最后给出完整的判断函数
bool Solution(const string& str){
int A, B;
if(str.find("root") < str.length()){
sscanf(str.c_str(), "%d", &A);
return A == Root;
}
else if(str.find("siblings") < str.length()){
sscanf(str.c_str(), "%d and %d", &A, &B);
if(A == B) return false;
return pre[A] == pre[B];
}
else if(str.find("parent") < str.length()){
sscanf(str.c_str(), "%d is the parent of %d", &A, &B);
return l[A] == B || r[A] == B;
}
else if(str.find("left") < str.length()){
sscanf(str.c_str(), "%d is the left child of %d", &A, &B);
return l[B] == A;
}
else if(str.find("right") < str.length()){
sscanf(str.c_str(), "%d is the right child of %d", &A, &B);
return r[B] == A;
}
else if(str.find("same level") < str.length()){
sscanf(str.c_str(), "%d and %d", &A, &B);
return Level[A] == Level[B];
}
else if(str.find("full tree") < str.length()){
return IsFullTree(Root);
}
}
完整程序
//
// Created by trudbot on 2022/6/22.
//结果: Accepted 通过了 11/11个数据 运行时间: 22 ms 运行空间: 216 KB
#include <bits/stdc++.h>
#define MaxNum 1001
using namespace std;
int l[MaxNum], r[MaxNum], pre[MaxNum];
int Root;
int inorder[31], postorder[31];
int Level[MaxNum];
int BuildTree(int li, int ri, int lp, int rp){
if(li > ri){
return 0;
}
int root = postorder[rp];
int i;
for(i=li; i<=ri; i++){
if(inorder[i] == root){
break;
}
}
l[root] = BuildTree(li, i-1, lp, lp+i-li-1);
if(l[root] != 0){
pre[l[root]] = root;
}
r[root] = BuildTree(i+1, ri, rp+i-ri, rp-1);
if(r[root] != 0){
pre[r[root]] = root;
}
return root;
}
void getLevel(int root, int level){
if(root == 0){
return;
}
Level[root] = level;
getLevel(l[root], level+1);
getLevel(r[root], level+1);
}
bool IsFullTree(int root){
if((r[root] == 0) && (l[root] == 0)){//叶子结点
return true;
}
if((r[root] == 0) ^ (l[root] == 0)){//度为1的结点
return false;
}
return IsFullTree(l[root]) && IsFullTree(r[root]);
}
bool Solution(const string& str){
int A, B;
if(str.find("root") < str.length()){
sscanf(str.c_str(), "%d", &A);
return A == Root;
}
else if(str.find("siblings") < str.length()){
sscanf(str.c_str(), "%d and %d", &A, &B);
if(A == B) return false;
return pre[A] == pre[B];
}
else if(str.find("parent") < str.length()){
sscanf(str.c_str(), "%d is the parent of %d", &A, &B);
return l[A] == B || r[A] == B;
}
else if(str.find("left") < str.length()){
sscanf(str.c_str(), "%d is the left child of %d", &A, &B);
return l[B] == A;
}
else if(str.find("right") < str.length()){
sscanf(str.c_str(), "%d is the right child of %d", &A, &B);
return r[B] == A;
}
else if(str.find("same level") < str.length()){
sscanf(str.c_str(), "%d and %d", &A, &B);
return Level[A] == Level[B];
}
else if(str.find("full tree") < str.length()){
return IsFullTree(Root);
}
}
int main() {
int N;
cin >> N;
for(int i=0; i<N; i++)
cin >> postorder[i];
for(int i=0; i<N; i++)
cin >> inorder[i];
Root = BuildTree(0, N-1, 0, N-1);
getLevel(Root, 1);
int M;
cin >> M;
getchar();
string str;
while(M--){
getline(cin, str);
if(Solution(str)){
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}
}
return 0;
}