Special topic of binary tree -- acwing 1497 Traversal of the tree (use post and mid order traversal to build a binary tree)

This question is very important , Whether in algorithm competition , Or in the written examination interview , Often appear .

The question ：

Tell us about a binary tree In the sequence traversal and After the sequence traversal , Want us to output its Sequence traversal （ namely BFS order ）

Ideas ：

First use the binary tree Middle order traversal and post order traversal , Build a binary tree , after utilize BFS Output the sequence of sequence traversal .

We simulation The following example The building process ：

according to In the question Sample Input, We know that for a given binary tree in 、 After the sequence traversal ：

• Middle preface ：1 2 3 4 5 6 7
• In the following order ：2 3 1 5 7 6 4

First , about After the sequence traversal Come on , The root node must be the last point , therefore “4” It must be the root node . after , We find “4” Number point , In the middle order traversal , We must be “4” Traverse the left subtree to the left of the dot （ Three points ：1 2 3）, Traverse the right subtree on its right （ Three points ：5 6 7）.

because Postorder traversal is to traverse the left subtree first , Post traversal right subtree , Last traversal root . According to the previous conclusion 4 Point left 、 The size of the right subtree is 3, So we found that , The post order traversal of the left subtree should be ：2 3 1（ The size is also 3）, The postorder traversal of the right subtree is ：5 7 6.

• We try to Recurse one layer to the left （4 Node number left subtree ）, Because we got the post order traversal of the left subtree （2 3 1）, according to “ The root node of post order traversal is the last point ” The principle of The root node of the left subtree is 1, After that In the sequence traversal Find 1 The position of point , Find out 1 There is no node on the left side of point , explain 1 The left subtree of point is empty , On the right 2 A little bit 2 3, namely ：1 The right subtree of node No. contains nodes 2 3. In post order traversal , because 2 3 It is the result of post order traversal , therefore 3 Namely 1 The root node of the right subtree of node No , stay Middle order traversal 2 stay 3 The left side of the , thus , We will 1 The left subtree of node number It's set up .

• Recurse one layer to the right （4 Node number right subtree ）, Similar to the above analysis process is not difficult to get .

For example , We The resulting binary tree as follows ：

To sum up , This topic should grasp two cores ：

• In subsequent traversal , The last point must be the root node
• stay Middle order traversal , First find the root node The location of , The left subtree is on the left side of the heel , The right subtree is on the right side of the root

among , In the middle order traversal, you can Using a hash table O(1) Complexity find Location of the root node .

We For the purpose of code implementation , Further abstract the process ：

• Each time we find the position of the middle root in the middle order traversal , This location left by Left subtree middle order traversal , On the right side by Order traversal in right subtree , Next you can see Left subtree interval length （ How many nodes are included ）.

• In post order traversal , We must be First traverse the left subtree , Post traversal right subtree , Finally, traverse the root node , thus , Left 、 In the right subtree 、 Post order traversal has been found , Next Recursive left subtree （ namely Given the middle order traversal and post order traversal of the left subtree , Recursive construction of left subtree ）, The right subtree recursively .

• Rebuild the whole tree recursively ： The current node is the root , The left side of the root recursively constructs the left subtree , Return to the root node of the left subtree , and Insert the root node of the left subtree into the left son of the root , Similarly, right subtree .

If we Treat each node in the tree as a separate root node , Then the whole recursive process is equivalent to Find the root node every time and insert , Build up gradually , It's better to understand .

So we can build the whole tree . After building the whole tree , Start at the root node BFS that will do .

above The complexity of the whole process is O(n) , Each node is processed once . Input to ensure that the weights of all points are different , If the ownership value is the same, it cannot be in O(n) The time complexity of （ The corresponding binary tree may not be unique ）

Code ：

（ Without notes , There are some changes based on the code below ）

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

using namespace std;
#define int long long
#define map unordered_map
const int N = 40;
int in[N], post[N];
map<int, int> l, r, d;

int build(int il, int ir, int pl, int pr)
{
    if(pl > pr) return 0;
    int root = post[pr];
    int k = d[root];
    l[root] = build(il, k - 1, pl, k - 1 - il + pl);
    r[root] = build(k + 1, ir, k - il + pl, pr - 1);
    return root;
}

void bfs(int root)
{
    queue<int> q; q.push(root);
    cout << root << ' ';

    while (!q.empty())
    {
        int t = q.front(); q.pop();

        if(l[t]) cout << l[t] << ' ', q.push(l[t]);

        if(r[t]) cout << r[t] << ' ', q.push(r[t]);
    }
    puts("");
}

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

    while (T--)
    {
        int n; cin >> n;
        for (int i = 0; i < n; ++i) cin >> post[i];
        for (int i = 0; i < n; ++i) cin >> in[i], d[in[i]] = i;
        int root = build(0, n - 1, 0, n - 1);
        bfs(root);
    }

    return 0;
}

（ add comments of explanations ）

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

using namespace std;
#define int long long
#define map unordered_map
const int N = 40;
int in[N], post[N];	// In the sequence traversal   After the sequence traversal 
map<int, int> l, r, d;	// respectively ： At every point   Left son   Right son  , The subscript corresponding to each node in the middle order traversal 

int build(int il, int ir, int pl, int pr)	// The current subtree   The left and right endpoints of the middle order traversal   Left and right endpoints of post order traversal 
{
    
	int root = post[pr];	// After traversing the last point   Root node 
	int k = d[root];	// Look up the table , Find the root node subscript in the middle order traversal 

	// If we treat each node in the tree as a separate root node , Then the whole recursive process is equivalent to finding the root node every time and building the tree step by step , It's better to understand 
	
	// The parameters passed recursively below   According to the following 、 The principle of medium order traversal , And solve the equation by using the principle of equal length of two ergodic intervals   To make sure , It's nice to draw pictures on paper 
	
	if (il < k) l[root] = build(il, k - 1, pl, k - 1 - il + pl);
	if (ir > k) r[root] = build(k + 1, ir, k - il + pl, pr - 1);
	return root;	// The return value is the root node 
}

void bfs(int root)
{
    
	queue<int> q; q.push(root);
	cout << root << ' ';

	while (!q.empty())
	{
    
		int t = q.front(); q.pop();
		
		if (l.count(t)) {
    
			cout << l[t] << ' ';
			q.push(l[t]);
		}

		if (r.count(t)) {
    
			cout << r[t] << ' ';
			q.push(r[t]);
		}
	}
	puts("");
}

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

	while (T--)
	{
    
		int n; cin >> n;
		for (int i = 0; i < n; ++i) cin >> post[i];	// In the following order 
		for (int i = 0; i < n; ++i) cin >> in[i], d[in[i]] = i;	// Middle preface   At the same time, save each subscript in the hash table 
		int root = build(0, n - 1, 0, n - 1);	// Recursively construct the whole binary tree 
		bfs(root);
	}

	return 0;
}