Tree reconstruction (pre order + middle order or post order + middle order)

I feel it is the simplest to write recursively

Before the order + Middle preface

#include<iostream>
#include<string>
#include<set>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int zhong[40], qian[40];
int root = 0;
typedef struct node* Node;
struct node {
    
	int data;
	Node left;
	Node right;
};
void Cen_Travel(Node T){
    };
// Functions of sequence traversal 
void BuildTree(Node& T, int beg, int end) {
    
// The pointer points to just a piece of space , You can only modify the contents of the space , You want to change the point of the pointer , You need to pass in the address of the pointer 
	int pos = -1;// Used to locate the position of the root node in the sequence 
	for (int i = beg; i <= end; i++)
	{
    
		if (zhong[i] == qian[root]) {
    
			pos = i;
			break;
		}
	}
	if (pos == -1) {
    
		T = NULL;
		return;
	}
	T = new struct node;
	T->data = qian[root];
	root++;
	// You must first left the subtree , Then the right subtree , You can't change the order , Later said 
	BuildTree(T->left, beg, pos-1);
	BuildTree(T->right, pos+1, end);
	
}
int main()
{
    
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> zhong[i];
	for (int i = 0; i < n; i++)
		cin >> qian[i];

	Node T;
	BuildTree(T, 0, n-1);
	Cen_Travel(T);
   return 0;
}

In the following order + Middle preface

int root = n-1;
void BuildTree(Node &node,int beg, int end)
{
    
	int pos = -1;
	for (int i = beg; i <= end; i++) {
    
		if (zhong[i] == hou[root]) {
    
			pos = i;
			break;
		}
	}
	if (pos == -1) {
    
		node = NULL;
		return;
	}
	node = new struct node;
	node->data = hou[root];
	root--;
	// The order from right to left cannot be changed 
	BuildTree(node->right, pos + 1, end);
	BuildTree(node->left, beg, pos-1);
}

explain

（ Preorder is to access the root node first , The first step is to access the root node in the middle , The last step is to access the root node ）

It is recommended to use it in conjunction with recursive traversal code

1. Why do you order first + Middle order is first left subtree and then right subtree , Posterior order + The middle order is reversed ：

Preface ：

Let's first look at how the preorder traverses .
First visit the root node And then I go through the left subtree , Finally, traverse the right subtree .

So the first node of our output sequence must be the root node of the tree , Then we visit the left subtree first , The second node is the current subtree （ The left subtree ） The root node , Then continue to visit the left subtree , So the third node is the root node of the current subtree …
So we root++ You can find the root node of each subtree step by step . This subtree in the middle order sequence corresponds to [beg,end], The left subtree of this subtree is [beg,pos-1], The right subtree is [pos+1,end].
So first reconstruct the left subtree .

In the following order ：

After the sequence in the same way , The following sequence is the last access to the root node , So the last node is the root node of the whole tree . Because first access the left subtree and then access the right subtree , So the post sequence is close to root Is a right subtree . our rot from n-1 Start , So close to root The node of is root The right subtree of the corresponding tree , So first reconstruct the right subtree , The left subtree is only after the reconstruction of the right subtree .

summary

The antecedent root is on the left , near root Is a left subtree , First reconstruct the left subtree .
Postorder root on the right , near root Is a right subtree , Rebuild the right subtree first .