题解：UVA12347 Binary Search Tree

· · 题解

题目大意

输入一棵二叉搜索树的前序遍历，求它的后序遍历。

分析

题面已经告诉了我们二叉搜索树的性质：

节点的左子树只包含键值小于该节点键值的节点。

节点的右子树只包含键值大于该节点键值的节点。

左子树和右子树也都必须是二叉搜索树。

以下内容来自 OI-Wiki：

空树是二叉搜索树。

若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。

若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。

二叉搜索树的左右子树均为二叉搜索树。

那么可以得到二叉搜索树最重要的性质之一：二叉搜索树的中序遍历就是点权的升序排序。

所以，输入前序遍历后排序即可得到中序遍历。

然后本题就成了已知二叉树的前序遍历、中序遍历，求后续遍历的板子题。

洛谷上的类似题：P1030

一本通上的板子原题：1339

其他

本题很奇妙的一点是没有事先告知有几个输入，因此我们要这样输入：

while(cin>>a){
    //do something
}

这样当输入结束时 while 循环会自动结束，在本地测试时按 Ctrl+Z 即可结束输入。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4+5;
int n,front[N],mid[N];//a 为前序遍历，b 为中序遍历
void dfs(int left_1,int right_1,int left_2,int right_2) {
    int now = lower_bound(mid,mid+n,front[left_1])-mid;
    if(now > left_2) func(left_1+1,left_1+now-left_2,left_2,now-1);
    if(now < right_2) func(left_1+now-left_2+1,right_1,now+1,right_2);
    cout<<front[left_1]<<'\n';
    return;
}
signed main() {
    n = 1;
    while(cin>>front[n]) {
        n++;
    }
    for(int i = 1;i <= n;i++) mid[i] = front[i];
    sort(mid+1,mid+n+1);//排序得中序遍历
    dfs(1,n,1,n);
    return 0;
}