Special topic of binary tree -- acwing 1589 Building binary search tree

The question ：

Regulations 0 Node number is the root node , The title gives The parent-child relationship between each numbered node , as well as A series of different weights .

basis Definition of binary search tree , Different weights will be given Insert and build a binary search tree .

Require output to build Sequence traversal of binary search tree （BFS order ）

Ideas ：

We know , Of a binary search tree The middle order traversal must be ordered , therefore , We must first put the question in A given series of weights are arranged in order .

After arranging the order , According to the middle order of the tree Set the ownership value Fill in the tree that will do .

Last , Output the sequence whose width first traversal that will do .

The general idea is like this , Let's talk about Code details .

about Each node in the binary search tree , I'm more used to using a method similar to the segment tree storage node , Use one Array of structs bst.

const int N = 110;
struct node
{
    int val; 
    int l, r;
} bst[N];

In the structure ,val Represents the weight of the current node ,l Represents the number of the left son ,r The number representing the right son （ namely Left and right pointer ）

Will input Weight array w After arranging the order , We can Use dfs In the order of traversal It's time to build a tree （ take w The array fills the nodes in the tree ）.

from w Array in Subscript to be k = 0 The location of Start filling in

How to complete dfs Middle order traversal of ：

• If Current point u = -1, Expressed as Blank nodes . direct return to flash back .
• otherwise , First recursive left subtree dfs(bst[u].l, k); Post recursive right subtree dfs(bst[u].r, k);
• stay Recursive left 、 Between right subtrees when , We need to Traverse the current point , namely bst[u].val = w[k++];

void dfs(int u, int& k)
{
    if (u == -1) return;
    dfs(bst[u].l, k);
    bst[u].val = w[k++];
    dfs(bst[u].r, k);
}

When it's done , The original tree Breadth first traversal , With 0 Point number is the root node Traversal ：（ Be careful ： Output while traversing ）

void bfs(int u)
{
    queue<int> q; q.push(u);
    cout << bst[u].val << ' ';
    while (q.size())
    {
        int tt = q.front(); q.pop();
        if (bst[tt].l != -1) {
            q.push(bst[tt].l);
            cout << bst[bst[tt].l].val << ' ';
        }
        if (bst[tt].r != -1) {
            q.push(bst[tt].r);
            cout << bst[bst[tt].r].val << ' ';
        }
    }
    puts("");
}

Time complexity ：

$O(n)$

Code ：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
//#define int long long
//#define map unordered_map
const int N = 110;
int n;
struct node
{
    
    int val; 
    int l, r;
} bst[N];
int w[N];

void dfs(int u, int& k)
{
    
    if (u == -1) return;
    dfs(bst[u].l, k);
    bst[u].val = w[k++];
    dfs(bst[u].r, k);
}

void bfs(int u)
{
    
    queue<int> q; q.push(u);
    cout << bst[u].val << ' ';
    while (q.size())
    {
    
        int tt = q.front(); q.pop();
        if (bst[tt].l != -1) {
    
            q.push(bst[tt].l);
            cout << bst[bst[tt].l].val << ' ';
        }
        if (bst[tt].r != -1) {
    
            q.push(bst[tt].r);
            cout << bst[bst[tt].r].val << ' ';
        }
    }
    puts("");
}

signed main()
{
    
    int T = 1; //cin >> T;

    while (T--)
    {
    
        cin >> n;
        for (int i = 0; i < n; ++i)
        {
    
            cin >> bst[i].l >> bst[i].r;
        }
        for (int i = 0; i < n; ++i)
        {
    
            cin >> w[i];
        }
        sort(w, w + n);
        int k = 0;
        dfs(0, k);
        bfs(0);
    }

    return 0;
}