题解：UVA12347 Binary Search Tree

willAK · 2025-01-23 20:36:24 · 题解

题解：UVA12347 Binary Search Tree

题目大意

二叉搜索树是满足以下属性的二叉树：

• 节点的左子树只包含键值小于该节点键值的节点。
• 节点的右子树只包含键值大于该节点键值的节点。
• 左子树和右子树也都必须是二叉搜索树。

给定一棵二叉搜索树的前序遍历，你的任务是找出这棵树的后序遍历。

解题思路

第一种思路

考虑根据前序遍历把树建出来，由于作者太菜了，以下是建树的提交：

知道建树怎么写的人，出来让我学习一下。\ 于是我们考虑第二种思路。正片开始。

第二种思路

只要专注力惊人，即可发现这一棵二叉搜索树的中序遍历为所有数从小到大的排列。\ 接下来就是一道知道前序，中序求后序的板子题。

解题代码

#include<bits/stdc++.h>
using namespace std;
int a[10010],b[10010],n;
void build(int l1,int r1,int l2,int r2)
//当前范围在先序遍历中为[l1,r1]，在中序遍历中为[l2,r2] 
{
    int m=lower_bound(b,b+n,a[l1])-b;
    //在中序遍历中找到根的位置 
    if(m>l2)
    {
        build(l1+1,l1+m-l2,l2,m-1);
    }
    if(m<r2)
    {
        build(l1+m-l2+1,r1,m+1,r2);
    }
    cout<<a[l1]<<"\n";
}
int main()
{
    while(cin>>a[n])
    {
        n++;
    }
    for(int i=0;i<n;i++) b[i]=a[i];
    sort(b,b+n);//中序遍历（排序）
    build(0,n-1,0,n-1);//遍历
    return 0;//完结撒花
}

最后，祝大家新年快乐！

---------------------------------
           /\
          ( *)======/\====
           )(      /  \ 
__________/  )    /    \
\___         /   / ""   \ 
  \____    _/   / (**)   \
     / \__/    (----------)
    /____|__//_ (  送给  )
         |      ( 亲爱的 )
         |       (      )
         |        (谷民)
        _|__
         \\    ☆新年 . 快乐☆