题目解析
本质是思维题,找规律. 本题就是那种思维难道很大,但是编码简单的题目.
核心: 找到规律,单子结点模式的确定
这是一个非常经典的二叉树计数问题。要解决这个问题，我们需要理解为什么“前序遍历 + 后序遍历”无法唯一确定一棵二叉树，以及这种“不确定性”是如何产生的。
核心思路解析
1. 为什么会不确定？
- 前序遍历 (Preorder)：根 -> 左 -> 右
- 后序遍历 (Postorder)：左 -> 右 -> 根
如果一个节点 Root 有两个孩子（左孩子 L 和 右孩子 R）：
- 前序：
Root L... R... - 后序：
L... R... Root我们可以清晰地分辨出L结束和R开始的边界，结构是唯一的。
但是，如果一个节点 Root 只有一个孩子 Child：
-
情况 A（
Child是左孩子）： -
前序：
Root Child... -
后序：
Child... Root -
情况 B（
Child是右孩子）： -
前序：
Root Child... -
后序：
Child... Root
关键发现：当节点只有一个孩子时，无论是作为左孩子还是右孩子，它的前序和后序遍历序列是完全一样的。 这意味着，每一个“只有一个孩子的节点”，都会带来两种可能性（左或右）。
2. 计算公式
如果我们在整棵树中发现了 个这样的“只有一个孩子的节点”，那么可能的中序遍历总数就是：
（因为每个这样的节点都有 2 种选择，根据乘法原理，总数是
3. 如何在字符串中检测这种情况？
我们需要在前序和后序字符串中找到这种特征：
- 在前序中：
A紧跟着B（即AB），表示A是B的父节点。 - 在后序中：
B紧跟着A（即BA），表示A的子树是以B结尾的。
判据：
如果在前序遍历中出现了 ... A B ...，且在后序遍历中出现了 ... B A ...，这就意味着 B 是 A 的唯一直接子节点（或者更准确地说，我们无法区分 A 到底只有左孩子 B 还是只有右孩子 B，但这正是我们需要计数的歧义点）。
反证：
如果 A 有两个孩子 B（左）和 C（右）：
- 前序：
... A B ... C ... - 后序：
... B ... C A ...此时前序是AB，但后序是CA。B和A在后序中不相邻。
算法步骤
- 读取前序字符串
s1和后序字符串s2。 - 初始化答案
ans = 1。 - 遍历前序字符串
s1，考察每一对相邻字符s1[i]和s1[i+1]。 - 在后序字符串
s2中找到这两个字符的位置。 - 如果它们在
s2中也是相邻的（顺序相反，即s1[i+1]在s1[i]的前一位），说明发现了一个“单子节点”结构。 - 每发现一个，
ans乘以 2。 - 输出
ans。
C++ 代码实现
cpp
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int main() {
string pre, post;
cin >> pre >> post;
long long ans = 1;
// 遍历前序字符串，注意范围是 0 到 length-2
// 因为我们要访问 pre[i] 和 pre[i+1]
for (int i = 0; i < pre.length() - 1; i++) {
char root = pre[i];
char child = pre[i+1];
// 在后序遍历中找到 root 和 child 的位置
// 实际上我们只需要判断：在 post 中，child 是否紧挨在 root 之前
// 找到 root 在 post 中的位置
int rootIdx = post.find(root);
// 找到 child 在 post 中的位置
int childIdx = post.find(child);
// 如果 child 正好在 root 的前一位
if (rootIdx == childIdx + 1) {
ans *= 2;
}
}
cout << ans << endl;
return 0;
}
举例图解验证
输入：
pre: abc
post: cba
- i=0:
pre[0]='a',pre[1]='b'. (对a和b关系进行检查)
- 在
post中，b的下标是 1，a的下标是 2。 2 == 1 + 1，满足条件！ans变 2。- 解释：
a只有一个孩子b，b可以是左或是右。
- i=1:
pre[1]='b',pre[2]='c'. (对b和c关系进行检查)
- 在
post中，c的下标是 0，b的下标是 1。 1 == 0 + 1，满足条件！ans变 4。- 解释：
b只有一个孩子c，c可以是左或是右。
- 输出 4。正确。