PAT A1043 Is It a Binary Search Tree [二叉查找树及遍历]

ゝ一世哀愁。 2021-10-23 15:50 191阅读 0赞

## 题目描述 ##

[链接][Link 1]  
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果

## 分析 ##

*  注意每个地方二叉查找树的定义不同，看清题目
 *  写insert函数的时候，不要忘记左右子树为NULL
 *  镜像二叉查找树实际就是遍历的时候，把左右次序更换下就好了！

#include<bits/stdc++.h> using namespace std; const int maxn = 1005; struct node{ int data; node *lchild; node *rchild; }nodes[maxn]; int a[maxn], n; void insert(node *&root, int x){ if(root == NULL){ root = new node; root->data = x; root->lchild = NULL; //不要忘记! root->rchild = NULL; //不要忘记! return; } if(x < root->data) insert(root->lchild, x); //题目定义不同 else insert(root->rchild, x); } node *create(){ node *root = NULL; for(int i=0;i<n;i++){ insert(root, a[i]); } return root; } vector<int> b,c,d; void preorder(node *root){ if(root==NULL) return; b.push_back(root->data); preorder(root->lchild); preorder(root->rchild); } void preorder2(node *root){ if(root==NULL) return; c.push_back(root->data); preorder2(root->rchild); preorder2(root->lchild); } void postorder(node *root){ if(root==NULL) return; postorder(root->lchild); postorder(root->rchild); d.push_back(root->data); } void postorder2(node *root){ if(root==NULL) return; postorder2(root->rchild); postorder2(root->lchild); d.push_back(root->data); } int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } node *root = create(); preorder(root); preorder2(root); bool flag1 = true, flag2 = true; for(int i=0;i<n;i++){ if(a[i] != b[i]) {flag1 = false; break;} } for(int i=0;i<n;i++){ if(a[i] != c[i]) {flag2 = false; break;} } if(flag1){ postorder(root); cout<<"YES"<<endl; for(int i=0;i<n;i++){ if(i==0) cout<<d[i]; else cout<<" "<<d[i]; } cout<<endl; }else if(flag2){ postorder2(root); cout<<"YES"<<endl; for(int i=0;i<n;i++){ if(i==0) cout<<d[i]; else cout<<" "<<d[i]; } cout<<endl; }else{ cout<<"NO"<<endl; } }

转载于:https://www.cnblogs.com/doragd/p/11270835.html

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805440976633856