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.
- If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST.
Now given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N integer keys are given in the next line. All the numbers in a line are separated by a space.Output Specification:
For each test case, first print in a line YES if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or NO if not. Then if the answer is YES, print in the next line the postorder traversal sequence of that 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 1:
7
8 6 5 7 10 8 11
Sample Output 1:
YES
5 7 6 8 11 10 8
Sample Input 2:
7
8 10 11 8 6 7 5
Sample Output 2:
YES
11 8 10 7 5 6 8
Sample Input 3:
7
8 6 8 5 10 9 11
Sample Output 3:
NO
算法思路简单描述:先不管是不是BST,先根据输入序列,插入建树(BST),如果建完之后的树,它的前序遍历与所给序列相同,那么所给的序列显然是可以构成BST的,应该给出YES,当然所给的序列还应和镜像的遍历比较,如果相同,也可以给出YES。
所以可以用三个数组存(输入序列,树的前序遍历,镜像树的前序遍历),但因为数组不太好比较,用vector更加方便,因为它重载了==符号。#includeusing namespace std;int N;struct node{ int data; node* lchild; node* rchild;};void insert(node* &root,int data){ if(root==NULL){ root=new node; root->data=data; root->lchild=root->rchild=NULL; return; } if(data data)insert(root->lchild,data); else insert(root->rchild,data);}void preOrder(node* root,vector & vi){ if(root==NULL)return; vi.push_back(root->data); preOrder(root->lchild,vi); preOrder(root->rchild,vi);}void preOrderMirror(node* root,vector & vi){ if(root==NULL)return; vi.push_back(root->data); preOrderMirror(root->rchild,vi); preOrderMirror(root->lchild,vi);}void postOrder(node* root,vector & vi){ if(root==NULL) return; postOrder(root->lchild,vi); postOrder(root->rchild,vi); vi.push_back(root->data);}void postOrderMirror(node* root,vector & vi){ if(root==NULL) return; postOrderMirror(root->rchild,vi); postOrderMirror(root->lchild,vi); vi.push_back(root->data);}vector origin,pre,preM,post,postM;int main(){ cin>>N; int data; node* root=NULL;// final root for(int i=0;i