二叉树专题--洛谷 P1229 遍历问题（乘法原理 已知前、后序遍历求中序遍历个数）

遍历问题

题目描述

我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：

所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。

输入格式

输A数据共两行，第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。

输出格式

输出可能的中序遍历序列的总数，结果不超过长整型数。

样例 #1

样例输入 #1

abc                           
cba

样例输出 #1

4

提示

无提示

题意：

给定一棵二叉树的 前、后序遍历，可知得到的 中序遍历不唯一，求得并输出 二叉树中序遍历的个数。

思路：

题目的要求是 求中序遍历的结果有多少种

二叉树 子结点的情况无异于 4 种：

• 左右子树、左子树、右子树、空，

在 这 4 种情况里 某结点 有左右子树 和 结点子树为空 的情况下 中序遍历是固定的，

所以 只有一个结点的情况才会出现中序遍历结果会有两种的情况，所以对于问题的探讨可以转换成：

• 通过前序和后序我们可以知道BinTree 中有多少个结点只有一个子树

对于 只有一个子树 的结点(即 a 只有一个子树 b)，我们可以发现其在 前序和后序中 的规律为：

• 在 PreOrder 中 a 的后继是 b，在 PostOrder 中 a 的前驱是 b

那么就 遍历前序和后序，cnt 表示有多少个符合条件的结点，每有一个这样的结点 意味着 BinTree 就会多 2 种结果（左 or 右）所以最后的结果就是 2 的 cnt 次方（乘法原理）

时间复杂度：

$O(n^2)$

代码：

#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;
}