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复习先序遍历和后序遍历，建树等操作。 要注意的是，参数值和返回值如果是node的话，均是返回指针变量node*，反正有关建树的题必须多做几遍。 建树要通过插入函数来建树，插入函数在bst中是递归调用的，递归边界是如果当前结点是空节点，就真正的插入，root = new Node（很重要），因为空结点是没有Node里的属性的，并把当前结点的值赋为val，左右子树均为空结点。如果要插入的值小于当前结点，就去左子树中继续插入。如果大于等于当前结点，就去右子树中继续插入。 在buildTree函数中，对题目给定的序列中每个值都进行插入操作。 如果需要当前树的镜像树的先序遍历，只要改变递归左右子树的顺序即可，后序也是
#include<iostream> #include<vector> using namespace std; int n; vector<int> preOrder; struct Node{ int data; Node *lchild, *rchild; }; void insert(Node* &root, int val){ if(root == nullptr){ root = new Node; root->data = val; root->lchild = nullptr; root->rchild = nullptr; return; } else if(val < root->data){ insert(root->lchild, val); } else{ insert(root->rchild, val); } } Node* buildTree(Node* root){ for(int i =0; i < n; i++){ insert(root,preOrder[i]); } return root; } vector<int> pre, post, mirpre, mirpost; void preTrave(Node* root){//bst的前序遍历 if(root == nullptr) return; pre.push_back(root->data); preTrave(root->lchild); preTrave(root->rchild); } void mirpreTrave(Node* root){//bst的镜像的前序遍历 if(root == nullptr) return; mirpre.push_back(root->data); mirpreTrave(root->rchild); mirpreTrave(root->lchild); } void postTrave(Node* root){//bst的后序遍历 if(root == nullptr) return; postTrave(root->lchild); postTrave(root->rchild); post.push_back(root->data); } void mirpostTrave(Node* root){//bst镜像的后序遍历 if(root == nullptr) return; mirpostTrave(root->rchild); mirpostTrave(root->lchild); mirpost.push_back(root->data); } int main(){ int x; cin>>n; for(int i = 0; i < n; i++){ cin>>x; preOrder.push_back(x); } Node* root = nullptr; root = buildTree(root); preTrave(root); mirpreTrave(root); postTrave(root); mirpostTrave(root); if(preOrder == pre){ cout<<"YES"<<endl; for(int i = 0; i < post.size(); i++){ if(i!=0) cout<<" "; cout<<post[i]; } } else if(preOrder == mirpre){ cout<<"YES"<<endl; for(int i = 0; i < mirpost.size(); i++){ if(i!=0) cout<<" "; cout<<mirpost[i]; } } else cout<<"NO"<<endl; return 0; }二刷，根据前序遍历分别构建bst和mbst，mbst就是将大于等于的插在左子树。对这两个进行前序遍历，和初始序列进行比较，判断初始序列和哪个相等
#include<iostream> #include<vector> using namespace std; int n; vector<int> preOrder; vector<int> preOrderBst; vector<int> preOrdermBst; vector<int> postOrder; struct node{ int val; node* lchild, *rchild; }; node* insertBst(node* root, int val){ if(root == nullptr){ node* root = new node; root->val = val; root->lchild = root->rchild = nullptr; return root; } else if(val >= root->val) root->rchild = insertBst(root->rchild,val); else root->lchild = insertBst(root->lchild,val); return root; } node* insertmBst(node* root, int val){ if(root == nullptr){ node* root = new node; root->val = val; root->lchild = root->rchild = nullptr; return root; } else if(val >= root->val) root->lchild = insertmBst(root->lchild,val); else root->rchild = insertmBst(root->rchild,val); return root; } node* buildTree(node* rootBst, node* rootmBst,bool flag){ if(flag == true){ for(int i = 0; i < preOrder.size(); i++){ rootBst = insertBst(rootBst,preOrder[i]); } return rootBst; } else{ for(int i = 0; i < preOrder.size(); i++){ rootmBst = insertmBst(rootmBst,preOrder[i]); } return rootmBst; } } void preOrderTrave(node* v, bool flag){//true是将其加入bst的先序遍历中 if(v == nullptr) return; if(flag == true) preOrderBst.push_back(v->val); else preOrdermBst.push_back(v->val); preOrderTrave(v->lchild,flag); preOrderTrave(v->rchild,flag); } void postOrderTrave(node* v){ if(v == nullptr) return; postOrderTrave(v->lchild); postOrderTrave(v->rchild); postOrder.push_back(v->val); } int main(){ int x; cin>>n; for(int i = 0; i < n; i++){ cin>>x; preOrder.push_back(x); } //反正第一个是根，先把它按照bst来建树，然后这个bst进行先序遍历，如果先序序列和初始序列一样，就是~，再按照mbst来建树，判断是否是mbst node* rootBst = nullptr; node* rootmBst = nullptr; rootBst = buildTree(rootBst,rootmBst,true); rootmBst = buildTree(rootBst,rootmBst,false); preOrderTrave(rootBst,true); preOrderTrave(rootmBst,false); if(preOrder == preOrderBst){ cout<<"YES"<<endl; postOrderTrave(rootBst); for(int i = 0; i < postOrder.size(); i++){ if(i!=0) cout<<" "; cout<<postOrder[i]; } } else if(preOrder == preOrdermBst){ cout<<"YES"<<endl; postOrderTrave(rootmBst); for(int i = 0; i < postOrder.size(); i++){ if(i!=0) cout<<" "; cout<<postOrder[i]; } } else cout<<"NO"; return 0; }