PAT 1043 判断二叉搜索树
本题核心:
1.postorder[cnt++] = root
如何实现后序遍历?
后序遍历的思想是:先遍历左子树,然后右子树,最后根结点,所以在重建的时候是按照左右根的方式进行的递归,那么post存的就是左右根的遍历,就是后序,如果postorder[cnt++] = root放在两个if之前那么就是按照根左右的方式重建的,就是先序
2.解题前提: 怎么建树?
二叉树的左子树都小于根节点,右子树都大于等于根节点,因此其中序遍历为从小到大的序列。因此对前序遍历的序列排序即可得到中序遍历的序列,结合给出的前序遍历的序列即可求出答案
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int preorder[N], inorder[N], postorder[N];
int cnt; //维护postorder的长度
//本题不需要中序遍历序列中value--->idx,因为要找第一个或者最后一个和前序序列第一个value相等的位置,遍历一边即可
bool build(int il, int ir, int pl, int pr, int flag){
if(il > ir) return true;
int root = preorder[pl];
int k = -1;
//找中序里根节点的位置
if (flag == 0)
{
for (k = il; k <= ir; k ++ )
if (inorder[k] == root)
break;
if (k > ir) return false;
}
else
{
for (k = ir; k >= il; k -- )
if (inorder[k] == root)
break;
if (k < il) return false;
}
//左右子树建树 看看能不能建上
if(!build(il, k - 1, pl + 1, pl + 1 + (k - il - 1), flag)) return false;
if(!build(k + 1, ir, pl + 1 + (k - il - 1) + 1, pr, flag)) return false;
//上述左右根递归 刚刚好就是后序遍历结果 因此直接填入postorder
postorder[cnt ++] = root;
return true;
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++) {
cin >> preorder[i];
inorder[i] = preorder[i];
}
sort(inorder, inorder + n); //得到中序遍历结果
//建树 -- > 1.正常建 2.镜像建
if(build(0, n - 1, 0, n - 1, 0)){
cout << "YES" << endl;
for(int i = 0; i < cnt; i ++){
if(i) cout << ' ';
cout << postorder[i];
}
}
else{
reverse(inorder, inorder + n);
if(build(0, n - 1, 0, n - 1, 1)){
cout << "YES" << endl;
for(int i = 0; i < cnt; i ++){
if(i) cout << ' ';
cout << postorder[i];
}
}
else cout << "NO" << endl;
}
return 0;
}