Informatics Orsay all in one 1339: [example 3-4] find the post order traversal | Valley p1827 [usaco3.4] American Heritage

【 Topic link 】

ybt 1339：【 example 3-4】 To find the subsequent traversal
Luogu P1827 [USACO3.4] American blood American Heritage
Both questions are known preorder and middle order ergodic sequences , Find the postorder traversal sequence
The difference for ：【ybt 1339】 First enter the preorder traversal sequence , Then enter the middle order traversal sequence .【 Luogu P1827】 First enter the middle order traversal sequence , Then enter the preorder traversal sequence .

【 Topic test site 】

1. Binary tree

We know the antecedent 、 Middle order side path sequence , Find the postorder traversal sequence

【 Their thinking 】

solution 1：

Suppose the input middle order traversal sequence is ：DBAECH, The preorder traversal sequence is ABDCEF. Take this input as an example to discuss the solution of the problem .
The current problem to be solved is ： We know the antecedent 、 Middle order traversal sequence , Building a binary tree .

1. First, the first letter in the preorder traversal is the value of the root node of the tree （A）.
2. Then find the root node value in the middle order traversal sequence （A） The location of , The sequence to the left of the root value （DB） Is the middle order traversal sequence of the left subtree of the root node . The sequence to the right of the root value （ECF） Is the middle order traversal sequence of the right subtree of the root node .
3. In the preorder traversal sequence, the length of the sequence traversed according to the order in the left subtree , Find the preorder traversal sequence of the left subtree （BD）, And the preorder traversal sequence of the right subtree （CEF）.
4. Recursively call “ Known preorder in order traversal sequence to find binary tree ” Function of . Now we know the left subtree of the root node 、 Preorder of right subtree 、 Middle order traversal sequence , Then the left subtree and right subtree of the root node can be constructed （ Building subtrees is relative to building A A tree that is the root node , It's a small-scale problem , When solving large-scale problems recursively , The solution of the small-scale problem is considered to be known ）
5. With A Is the root node , Connect the constructed left and right subtrees , That is, the construction of the tree is completed .

Next, do post order traversal of this tree , You can get the post order traversal sequence of the tree .

How to write it 1： Use character array

Enter the sequence of first order traversal to s_pre, Middle order traversal sequence to character array s_in.
function createTree Need to ml,mr,pl,pr, Meaning for ： By a priori sequence s_pre[pl]~s_pre[pr] And middle order sequence s_in[ml]~s_in[mr] Construct a binary tree
According to the above algorithm , First, find the first character of the sequence in the middle sequence s_pre[pl] The location of , Find the location for i. Then the middle order traversal sequence of the left subtree is s_in[ml]~s_in[i-1], The length is i-ml, In the preorder traversal sequence , from pl+1 Start with the length i-ml Sequence , The position of the last element is pl+i-ml, Then the preorder traversal sequence of the left subtree is s_pre[pl+1]~s_pre[pl+i-ml]. Similarly , The middle order sequence of the right subtree can be obtained as s_in[i+1]~s_in[mr], The precedence sequence is s_pre[pl+i-ml+1]~s_pre[pr].
Use createTree Generate left and right subtrees respectively , Next to the newly assigned root node , You get this tree .
The recursive exit is ： The subscript range of preorder and middle order sequences must have pl<=pr And ml<=mr, If this condition is not met , Sequence range is meaningless , Should return to .

How to write it 2： Use string class

The idea is similar to the above method , I won't repeat .
Use string class , have access to substr Member function to get substring . The sequence of each incoming function 、 Middle order sequences are string Class object .

【 Solution code 】：ybt 1339：【 example 3-4】 To find the subsequent traversal

How to write it 1： Use character array

#include <bits/stdc++.h>
using namespace std;
#define N 1000
struct Node
{
    
    char val;
    int left, right;
};
Node node[N];
int p = 1;
char s_pre[105], s_in[105];//s_pre: First, we traverse the sequence  s_in: Middle order traversal sequence  
// By a priori sequence s_pre[pl]~s_pre[pr] And middle order sequence s_in[ml]~s_in[mr] Construct a binary tree , Return to root node  
int createTree(int pl, int pr, int ml, int mr)
{
    
    if(pl > pr || ml > mr)
        return 0;
    int np = p++, i;
    node[np].val = s_pre[pl];
    for(i = ml; i <= mr; ++i)
    {
    
        if(s_in[i] == s_pre[pl])
            break;
    }
    node[np].left = createTree(pl + 1, pl + i - ml, ml, i - 1);
    node[np].right = createTree(pl + i - ml + 1, pr, i + 1, mr);
    return np;
}
void postOrder(int root)
{
    
    if(root != 0)
    {
    
        postOrder(node[root].left);
        postOrder(node[root].right);
        cout << node[root].val;
    }
}
int main()
{
    
    cin >> s_pre >> s_in;
    int root = createTree(0, strlen(s_pre) - 1, 0, strlen(s_in) - 1);
    postOrder(root);
    return 0;
}

How to write it 2： Use string class

#include <bits/stdc++.h>
using namespace std;
#define N 1000
struct Node
{
    
    char val;
    int left, right;
};
Node node[N];
int p = 1;
string s_pre, s_in;
int createTree(string sp, string si)// Using a preorder sequence sp And middle order sequence si Building a binary tree , Return to tree root  
{
    
	int np = p++, i;
    node[np].val = sp[0];
	for(i = 0; i < si.length(); ++i)
    {
    
        if(sp[0] == si[i])
            break;
    }
    int len_l = i, len_r = si.length() - 1 - i;// The sequence length of left and right subtrees  
    if(len_l > 0)// The sequence length is greater than 0, To build a tree  
    	node[np].left = createTree(sp.substr(1, len_l), si.substr(0, len_l));
    if(len_r > 0)
		node[np].right = createTree(sp.substr(i+1, len_r), si.substr(i+1, len_r));
	return np;
}
void postOrder(int root)
{
    
    if(root != 0)
    {
    
        postOrder(node[root].left);
        postOrder(node[root].right);
        cout << node[root].val;
    }
}
int main()
{
    
    cin >> s_pre >> s_in;
    int root = createTree(s_pre, s_in);
    postOrder(root);
    return 0;
}

【 Solution code 】： Luogu P1827 [USACO3.4] American blood American Heritage

How to write it 1： Use character array

#include <bits/stdc++.h>
using namespace std;
#define N 1000
struct Node
{
    
    char val;
    int left, right;
};
Node node[N];
int p = 1;
char s_pre[105], s_in[105];//s_pre: First, we traverse the sequence  s_in: Middle order traversal sequence  
// By a priori sequence s_pre[pl]~s_pre[pr] And middle order sequence s_in[ml]~s_in[mr] Construct a binary tree , Return to root node  
int createTree(int pl, int pr, int ml, int mr)
{
    
    if(pl > pr || ml > mr)
        return 0;
    int np = p++, i;
    node[np].val = s_pre[pl];
    for(i = ml; i <= mr; ++i)
    {
    
        if(s_in[i] == s_pre[pl])
            break;
    }
    node[np].left = createTree(pl + 1, pl + i - ml, ml, i - 1);
    node[np].right = createTree(pl + i - ml + 1, pr, i + 1, mr);
    return np;
}
void postOrder(int root)
{
    
    if(root != 0)
    {
    
        postOrder(node[root].left);
        postOrder(node[root].right);
        cout << node[root].val;
    }
}
int main()
{
    
    cin >> s_in >> s_pre;
    int root = createTree(0, strlen(s_pre) - 1, 0, strlen(s_in) - 1);
    postOrder(root);
    return 0;
}

How to write it 2： Use string class

#include <bits/stdc++.h>
using namespace std;
#define N 1000
struct Node
{
    
    char val;
    int left, right;
};
Node node[N];
int p = 1;
string s_pre, s_in;
int createTree(string sp, string si)// Using a preorder sequence sp And middle order sequence si Building a binary tree , Return to tree root  
{
    
	int np = p++, i;
    node[np].val = sp[0];
	for(i = 0; i < si.length(); ++i)
    {
    
        if(sp[0] == si[i])
            break;
    }
    int len_l = i, len_r = si.length() - 1 - i;// The sequence length of left and right subtrees  
    if(len_l > 0)// The sequence length is greater than 0, To build a tree  
    	node[np].left = createTree(sp.substr(1, len_l), si.substr(0, len_l));
    if(len_r > 0)
		node[np].right = createTree(sp.substr(i+1, len_r), si.substr(i+1, len_r));
	return np;
}
void postOrder(int root)
{
    
    if(root != 0)
    {
    
        postOrder(node[root].left);
        postOrder(node[root].right);
        cout << node[root].val;
    }
}
int main()
{
    
    cin >> s_in >> s_pre;
    int root = createTree(s_pre, s_in);
    postOrder(root);
    return 0;
}