Description
It doesn’t make any sense, but you are now a member of the literature club in a high school.
Currently, the director (社長) of the literature club, Monica, is worried about her homework from computer science class (she takes this course in high school due to 多元學習). As an outstanding student, Monica always finished her homework fast and perfectly. However, she is not quite good at computer science. Monica knows you are a 二類生, thus she asks you for help with the homework during today's club time. The problem is described below:
Given a preorder traversal sequence and a postorder traversal sequence of a binary tree. Then, given an inorder traversal sequence, answer whether these three sequences can construct a valid binary tree.
You won't want to disappoint Monica, so you better hurry.
Hint from Yuri's notebook:
If you have no idea how to implement, please take it as your reference and thanks Yuri for her help.
By the way, Yuri wants to remind you that not every preorder sequence and inorder sequence could construct a binary tree. See sample input/output as reference.
#include <stdlib.h>
#include <stdio.h>
typedef struct _node {
int value;
struct _node *left;
struct _node *right;
} Node;
// create a new node
Node *create_node(int value);
// verify whether the postorder is match with the input
int verify(Node *root, int *postorder);
// free the memory
void destroy(Node *root);
/*
Parameter description:
int *inorder : the inorder traversal sequence of the binary tree.
int *preorder : the preorder traversal sequence of the binary tree.
int inorder_start : the starting index of the inorder traversal of the subtree.
int inroder_end : the ending index of the inorder traversal of the subtree.
As for the preorder traversal index, you can try declaring a global variable.
*/
// build the tree using recursive
Node *build(int *inorder, int *preorder, int inorder_start, int inorder_end);
Input
The first line of input contains an integer N, indicating the number of nodes on the tree.
The second line contains N distinct numbers, which is the preorder traversal sequence of the binary tree.
The third line contains N distinct numbers, which is the postorder traversal sequence of the binary tree.
Then, the fourth line contains an integer Q, indicating the number of queries.
The following Q lines each contain N distinct numbers, which is the inorder traversal sequence of the binary tree.
Constraints:
1 ≤ N ≤ 2 x 105
1 ≤ Q ≤ 20
For all x being the number on the binary tree, 0 ≤ x ≤ N-1.
Output
Output contains Q lines. For each query, print ‘Yes’ if the three sequences could construct a valid binary tree, otherwise print ‘No’.