Stl+ tree

"Code is beautiful and powerful that can changes the world"

                                                                                            --2021.8.23

subject :https://codeforces.com/problemset/problem/675/D

Carelessness : Construct a binary tree , Output... In sequence The parent node corresponding to the input value

Answer key :1. utilize set Sort storage nodes from small to large

        2. Consider the situation

AC Code :

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<set>
#include<map>
using namespace std;
const int N = 1e5;
int a[N+1];
int main()
{
	a[0] = 0;
	int n;
	while (scanf("%d", &n) != EOF)
	{
		set<int>s;
		scanf("%d", &a[1]);
		s.insert(a[1]);
		map<int, int>l, r;// Represents whether there are left and right subtrees 
		for (int i = 2; i <= n; ++i)
		{
			if (i > 2) { cout << " "; }
			scanf("%d", &a[i]);
			set<int>:: iterator add;// Get address 
			add = s.lower_bound(a[i]);// See if you can find a larger number 
			if (add == s.end())// It means that we didn't find 
			{
				printf("%d", *(--add));// Just take it as set The right subtree of the maximum in 
				r[*(add)] = 1;// Mark it as the right node of the parent node 
			}
			else// Find a larger number 
			{
				if (l[*add] == 1)// If the left subtree of the node already exists 
				{
					printf("%d", *(--add));// It is called its position -1 The right subtree of the previous node of 
					r[*(add)] = 1;
				}
				else// If the left subtree exists, it is regarded as the left subtree of the node 
				{
					printf("%d", *(add));
					l[*(add)] = 1;
				}
			}
			s.insert(a[i]);
		}
	}
	return 0;
}