【PAT甲级真题】- Is It a Binary Search Tree (25)
题目来源
Is It a Binary Search Tree (25)
题目描述点击链接自行查看
注意点：
- 这里的二叉搜索树大于等于插到右边
思路简介
一道二叉树模板题（6202年了应该不会还有人不会写二叉树吧bushi）
一开始想到前序遍历不可能确定一棵树还以为题目错了
后面发现题目说的是前序遍历是否有可能是一个二叉搜索树
那其实就是按照前序遍历的顺序以此把给出点插入到二叉搜索树当中
然后对建完的树进行一次前序遍历，如果结果相同，说明这个前序遍历是合法的，否则就是不合法的
然而题目中提到了镜像树也算
镜像其实也很简单，前序遍历的顺序是NLR即当前(now)-左边(left)-右边(right)
镜像操作就是NRL，判断镜像树只要按照正常的顺序插入之后看看镜像前序遍历是否和给出序列相同即可
注意，如果是镜像的，由于我们的插入是正常的顺序，所以镜像树输出后序遍历时必须也是镜像的，需要再写一个镜像后续遍历
遇到的问题
- 后序遍历没有镜像WA了一次
代码
/** * https://www.nowcoder.com/pat/5/problem/4082 * 二叉树遍历模板 */#include<bits/stdc++.h>usingnamespacestd;structTreeNode{intkey;TreeNode*right,*left;TreeNode():key(0),right(nullptr),left(nullptr){}TreeNode(intk):key(k),right(nullptr),left(nullptr){}};voidinsert(TreeNode*&root,TreeNode*node){if(!root){root=node;return;}if(node->key<root->key){insert(root->left,node);}else{insert(root->right,node);}}voidpreorder(TreeNode*root,vector<int>&res){if(!root)return;res.emplace_back(root->key);preorder(root->left,res);preorder(root->right,res);}voidmirro_preorder(TreeNode*root,vector<int>&res){if(!root)return;res.emplace_back(root->key);mirro_preorder(root->right,res);mirro_preorder(root->left,res);}voidpostorder(TreeNode*root,vector<int>&res){if(!root)return;postorder(root->left,res);postorder(root->right,res);res.emplace_back(root->key);}voidmirro_postorder(TreeNode*root,vector<int>&res){if(!root)return;mirro_postorder(root->right,res);mirro_postorder(root->left,res);res.emplace_back(root->key);}voidsolve(){intn;cin>>n;TreeNode*root=nullptr;vector<int>input(n);for(inti=0;i<n;++i){cin>>input[i];TreeNode*node=newTreeNode(input[i]);insert(root,node);}vector<int>res1,res2,res;preorder(root,res1);mirro_preorder(root,res2);if(res1==input){cout<<"YES\n";postorder(root,res);for(inti=0;i<n;++i)cout<<res[i]<<' ';return;}if(res2==input){cout<<"YES\n";mirro_postorder(root,res);for(inti=0;i<n;++i)cout<<res[i]<<' ';return;}cout<<"NO";}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//fstream in("in.txt",ios::in);cin.rdbuf(in.rdbuf());intt=1;//cin>>t;while(t--){solve();}return0;}