题目描述

二叉搜索树 (BST) 递归定义为具有以下属性的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉搜索树
给定二叉树的具体结构以及一系列不同的整数，只有一种方法可以将这些数填充到树中，以使结果树满足 BST 的定义。

请你输出结果树的层序遍历。

示例如图 1 和图 2 所示。

24c2521f-aaed-4ef4-bac8-3ff562d80a1b.jpg

输入格式
第一行包含一个正整数 N，表示树的结点个数。

所有结点的编号为 0∼N−1，并且编号为 0 的结点是根结点。

接下来 N 行，第 i 行（从 0 计数）包含结点 i 的左右子结点编号。如果该结点的某个子结点不存在，则用 −1 表示。

最后一行，包含 N 个不同的整数，表示要插入树中的数值。

输出格式
输出结果树的层序遍历序列。

数据范围
1≤N≤100
输入样例：
9
1 6
2 3
-1 -1
-1 4
5 -1
-1 -1
7 -1
-1 8
-1 -1
73 45 11 58 82 25 67 38 42
输出样例：
58 25 82 11 38 67 45 73 42

算法1

(模拟构造) $O(n)$

数据结构
{
tree
{
int l,r,data;
}

}
1.构造左右孩子：
左边和右边用l,r来表示
2.如何建立二叉搜索树将数据排序后 中序遍历就是二叉搜索树
dfs来搜索
3.bfs进来一个头结点,然后不断更新下一个左边先，后边

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n,co;
struct tree
{
    int l,r,data;
}p[110];
int num[110];
vector<int > ans;
void dfs(int u)
{
    if(u==-1) return ;
    dfs(p[u].l);
    p[u].data=num[co++];
    dfs(p[u].r);

}
void bfs()
{
    queue<tree> q;
    q.push(p[0]);
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        ans.push_back(t.data);
        if(t.l!=-1) q.push(p[t.l]);
        if(t.r!=-1) q.push(p[t.r]);
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;++i)
    {
        int l,r;
        cin>>l>>r;
        p[i].l=l;
        p[i].r=r;
    }
    for(int i=0;i<n;++i)
    {
        cin>>num[i];
    }
    sort(num,num+n);
    dfs(0);
    bfs();
    int f=0;
    for(auto x: ans)
    {
        if(f) cout<<" ";
        cout<<x;
        f=1;
    }

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla