A new parliament is elected in the state of MMMM. Each member of the parliament gets his unique positive integer identification number during the parliament registration. The numbers were given in a random order; gaps in the sequence of numbers were also possible. The chairs in the parliament were arranged resembling a tree-like structure. When members of the parliament entered the auditorium they took seats in the following order. The first of them took the chairman’s seat. Each of the following delegates headed left if his number was less than the chairman’s, or right, otherwise. After that he took the empty seat and declared himself as a wing chairman. If the seat of the wing chairman has been already taken then the seating algorithm continued in the same way: the delegate headed left or right depending on the wing chairman’s identification number.
The figure below demonstrates an example of the seating of the members of parliament if they entered the auditorium in the following order: 10, 5, 1, 7, 20, 25, 22, 21, 27.
During its first session the parliament decided not to change the seats in the future. The speech order was also adopted. If the number of the session was odd then the members of parliament spoke in the following order: the left wing, the right wing and the chairman. If a wing had more than one parliamentarian then their speech order was the same: the left wing, the right wing, and the wing chairman. If the number of the session was even, the speech order was different: the right wing, the left wing, and the chairman. For a given example the speech order for odd sessions will be 1, 7, 5, 21, 22, 27, 25, 20, 10; while for even sessions — 27, 21, 22, 25, 20, 7, 1, 5, 10.
Determine the speech order for an even session if the speech order for an odd session is given.
Input
The first line of the input contains N, the total number of parliamentarians. The following lines contain N integer numbers, the identification numbers of the members of parliament according to the speech order for an odd session.
The total number of the members of parliament does not exceed 3000. Identification numbers do not exceed 65535.
Output
The output should contain the identification numbers of the members of parliament in accordance with the speech order for an even session.
Example
| input | output |
|---|
9
1
7
5
21
22
27
25
20
10
|
27
21
22
25
20
7
1
5
10
|
题意规定：左结点<根结点<右结点
给出一棵二叉搜索树左子树+右子树+根的后序遍历，要求输出右子树+左子树+根的遍历顺序
思路
根据给出的遍历顺序可知最后一个节点一定是根节点，然后通过该根节点寻找它的左子树（所有节点小于根节点）和它的右子树（所有节点大于根节点），然后递归地先搜索右子树，再搜索左子树，最后输出根节点即可
1 #include <iostream>
2 using namespace std;
3 const int MAXN = 65536;
4 int arr[MAXN];
5
6 void fun(int l,int r)
7 {
8 int i=0;
9 while(i<r && arr[i]<arr[r]) i++;
10 if(i<r)
11 fun(i,r-1);
12 if(i>l)
13 fun(l,i-1);
14 cout << arr[r] << endl;
15 }
16
17 int main()
18 {
19 std::ios::sync_with_stdio(false);
20 cin.tie(0);
21 cout.tie(0);
22 int n;
23 cin >> n;
24 for(int i=0;i<n;i++)
25 cin >> arr[i];
26 fun(0,n-1);
27 return 0;
28 }
Parliament
原文：https://www.cnblogs.com/yzlzm/p/12589159.html
