PTA Advanced 1159 Structure of a Binary Tree C++
目录
题目
Input Specification:
Output Specification:
Sample Input:
Sample Output:
思路
代码
题目
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 N (≤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 M (≤30) is given, followed by M 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思路
这题也不是难题，可以在1167 Cartesian Tree 或1020 Tree Traversals的基础上对dfs函数进行改进，即在dfs函数里面统计当前子树的根节点的信息，包括：层次(level)、双亲(parent)和左右孩子(left、right)
关键技术：
1. 如何获取statement中的数字 --- --- 用正则表达式做匹配
在1164 Good in C这题中也用到了正则表达式匹配字符串，封装好的函数代码如下：
#include <regex>// 根据传入的正则表达式分割字符串
// str-即将要进行分割的字符串；sep-正则表达式；result-存放分割后结果的容器
void splitStringByRegex(string str,string sep,vector<int> &result){regex pattern(sep);sregex_token_iterator end;// 循环结束的标志 // 有-1时表示得到i是除正则表达式外的部分，没有-1时表示得到i是和正则表达式匹配的部分 for(sregex_token_iterator i(str.begin(),str.end(),pattern);i!=end;++i){ result.push_back(stoi(*i));}
}2. 如何判断statement是哪一类别 --- --- 用str1.find(str2)函数
// str1中找到了str2
if(str1.find(str2)!=string::npos){... ...
}else{// 没找到时... ...
}代码
#include <iostream>
#include <vector>
#include <string>
#include <regex>
#include <map>using namespace std;struct Node{int level;int parent;int left;int right;
};vector<int> postOrder,inOrder;
map<int,Node> nodes;
int hasOneChildNum=0; // 根据传入的正则表达式分割字符串
// str-即将要进行分割的字符串；sep-正则表达式；result-存放分割后结果的容器
void splitStringByRegex(string str,string sep,vector<int> &result){regex pattern(sep);sregex_token_iterator end;// 循环结束的标志 // 有-1时表示得到i是除正则表达式外的部分，没有-1时表示得到i是和正则表达式匹配的部分 for(sregex_token_iterator i(str.begin(),str.end(),pattern);i!=end;++i){ result.push_back(stoi(*i));}
}void dfs(int postLeft,int postRight, int inLeft,int inRight, int currentLevel, int parent){if(postLeft>postRight) return;// 当前子树的root是后序遍历序列的最后一个元素 int root=postOrder[postRight];// 确定root的level和parent Node node; node.level=currentLevel;node.parent=parent; // 找到子树根在中序遍历序列中的位置int rootIndex=inLeft;for(;rootIndex<=inRight;rootIndex++)if(inOrder[rootIndex]==root) break;// 左子树后序遍历序列的index范围：postLeft ~ postLeft+rootIndex-inLeft-1int leftTreeLeft=postLeft;int leftTreeRight=postLeft+rootIndex-inLeft-1;// 右子树后序遍历序列的index范围：postLeft+rootIndex-inLeft ~ postRight-1int rightTreeLeft=postLeft+rootIndex-inLeft;int rightTreeRight=postRight-1;// 确定root的左右孩子if(leftTreeRight>=leftTreeLeft) node.left=postOrder[leftTreeRight];else node.left=-1;if(rightTreeRight>=rightTreeLeft) node.right=postOrder[rightTreeRight];else node.right=-1;// 统计只有一个孩子的结点的数量if(node.left!=-1&&node.right==-1||node.left==-1&&node.right!=-1) hasOneChildNum++;nodes[root]=node;dfs(leftTreeLeft,leftTreeRight, inLeft,rootIndex-1, currentLevel+1, root);// 该树的左子树相同操作 dfs(rightTreeLeft,rightTreeRight, rootIndex+1,inRight, currentLevel+1, root);// 该树的右子树相同操作
}int main(int argc, char** argv) {int n;cin>>n;postOrder.resize(n);inOrder.resize(n);for(int i=0;i<n;i++) cin>>postOrder[i];for(int i=0;i<n;i++) cin>>inOrder[i];// 根据后序和中序遍历次序健全结点信息 dfs(0,n-1, 0,n-1, 0, -1); int m;cin>>m;cin.get();for(int i=0;i<m;i++){string statement; getline(cin,statement);// 从statement中获取结点data vector<int> nodeData;splitStringByRegex(statement,"[0-9]+",nodeData); bool flag=false;// statement是判断某个结点是否是树的根时 if(statement.find("root")!=string::npos){if(nodes[nodeData[0]].parent==-1) flag=true;}else if(statement.find("level")!=string::npos){// statement是判断两个结点是否在同一层时if(nodes[nodeData[0]].level==nodes[nodeData[1]].level) flag=true;}else if(statement.find("parent")!=string::npos){// statement是判断结点0是否是结点1的双亲if(nodes[nodeData[1]].parent==nodeData[0]) flag=true;}else if(statement.find("left")!=string::npos){// statement是判断结点0是否是结点1的左孩子 if(nodes[nodeData[1]].left==nodeData[0]) flag=true;}else if(statement.find("right")!=string::npos){// statement是判断结点0是否是结点1的右孩子 if(nodes[nodeData[1]].right==nodeData[0]) flag=true;}else if(statement.find("siblings")!=string::npos){// statement是判断结点0和结点1是否是兄弟 int parent=nodes[nodeData[0]].parent;if(nodes[parent].left==nodeData[1]||nodes[parent].right==nodeData[1]) flag=true;}else if(statement.find("full")!=string::npos){// statement是判断这棵树是否是一颗full树 if(hasOneChildNum==0) flag=true;}if(flag) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}