Special topic of binary tree -- Logu p1229 traversal problem (the number of traversals in the middle order is calculated when the pre and post order traversals of the multiplication principle are know

Ergodic problem

Title Description

We are all familiar with the preorder of binary trees 、 Middle preface 、 After the sequence traversal , Such problems are often raised in data structures ： We know the preorder and inorder traversal of a binary tree , Find its postorder traversal , Corresponding , Given the post order traversal and middle order traversal sequences of a binary tree, you can also find its pre order traversal . However, given the preorder and postorder traversal of a binary tree , But you can't be sure of the middle order traversal sequence , Consider several binary trees as shown in the figure below ：

All these binary trees have the same preorder traversal and postorder traversal , But the middle order traversal is different .

Input format

transport A There are two lines of data , The first line represents the preorder traversal result of the binary tree s1, The second line represents the post order traversal result of the binary tree s2.

Output format

Output the total number of possible middle order traversal sequences , The result does not exceed the number of long integers .

Examples #1

The sample input #1

abc                           
cba

Sample output #1

4

Tips

No prompting

The question ：

Given a binary tree front 、 After the sequence traversal , You can get Middle order traversal is not unique , Get and output The number of ordered traversals in a binary tree .

Ideas ：

The requirement of the title is How many kinds of results are there for finding the middle order traversal

Binary tree The situation of child nodes is no different from 4 Kind of ：

• Left and right subtrees 、 The left subtree 、 Right subtree 、 empty ,

stay this 4 In this case A node There are left and right subtrees and Node subtree is empty Under the circumstances The middle order traversal is fixed ,

therefore Only in the case of one node, there will be two cases of intermediate order traversal results , So the discussion of the problem can be transformed into ：

• Through the preface and postscript, we can know BinTree How many nodes in have only one subtree

about There is only one subtree The node of ( namely a There is only one subtree b), We can find it in In the preamble and postscript The law of is ：

• stay PreOrder in a The successor is b, stay PostOrder in a The precursor to this is b

then Traverse the pre order and post order ,cnt Indicates how many nodes meet the conditions , Every such node signify BinTree There will be more 2 Seed result （ Left or Right ） So the end result is 2 Of cnt Power （ Multiplication principle ）

Time complexity ：

$O(n^2)$

Code ：

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

using namespace std;
//#define int long long
//#define map unordered_map
string pre, post;

int solve()
{
    
	int cnt = 0;
	for (int i = 0; i < pre.size() - 1; ++i)
	{
    
		for (int j = 1; j < post.size(); ++j)
		{
    
			auto a = pre[i], b = post[j];
			if (a == b && pre[i + 1] == post[j - 1]) ++cnt;
		}
	}
	return (1 << cnt);
}

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

	while (T--)
	{
    
		cin >> pre >> post;
		cout << solve() << '\n';
	}

	return 0;
}