补全代码跑了一下，能过90%的数据，最后一组大数据超时了

这个算法时间复杂度太高了，因为每次都调dfs去递归查找位置

建议看一下这个题解：https://noobdream.com/post/370949/

#include<bits/stdc++.h>
using namespace std;
struct node{
    int val;
    node *left,*right;
    node(int a=0,node *p=NULL,node *q=NULL)
    {
        val=a;
        left=p;
        right=q;
    }
};
int n;
node *r=NULL;
void dfs(node *p,int x) //先找到位置，直到该结点为叶子结点
{
    if(p->left==NULL&&p->right==NULL)
    {
        if(x>p->val)
        {
            p->right=new node;
            p->right->val=x;
        }
        else
        {
            p->left=new node;
            p->left->val=x;
        }
        return;
    }

    if(x>p->val)
    {
        if(p->right!=NULL)
        dfs(p->right,x);
        else
        {
            p->right=new node(x);
        }
    }
    else if(x<p->val)
    {
        //if(x==1) cout << "**" << endl;
        if(p->left!=NULL)
        dfs(p->left,x);
        else p->left=new node(x);
    }
}
void cr(int x)
{

    if(r==NULL)
    {
        r=new node;
        r->val=x;
    }
    else
    {
        //if(x==1) cout << x << endl;
        node *p=r;
        dfs(p,x);
    }
}

vector<int> ans;
void dy(node *p,node *pre)
{
    if(p!=NULL)
    {
        if(p==r)
        {
            pre=p;
            ans[p->val]=0;
        }
        else
        {
            //pre=p;
            ans[p->val]=pre->val;
            pre=p;
        }
        dy(p->left,pre);
        dy(p->right,pre);
    }
}

int main()
{
    cin >> n;
    ans.resize(n+1);
    vector<int> p(n);
    for(int i=0;i<n;i++) cin >> p[i];
	for(int i=0;i<n;i++)
	{
		cr(p[i]);
	}

    dy(r,r);
    for(int i=1;i<=n;i++) cout << ans[i] << ' ';

}

咦，好像样例都没通过

5
2 3 5 1 4