| 题目名称 | 1112. 遍历问题 |
|---|---|
| 输入输出 | bianli.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 王者自由
于2012-10-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：14， 提交：51， 通过率：27.45% | ||||
 明天 |
100 | 0.001 s | 0.17 MiB | Pascal |
 Twist Fate |
100 | 0.002 s | 0.17 MiB | Pascal |
 wire |
100 | 0.002 s | 0.29 MiB | C++ |
 Zwoi_只会打表抄代码的蒟蒻 |
100 | 0.002 s | 0.29 MiB | C |
 超梦 |
100 | 0.002 s | 0.31 MiB | C++ |
 张寅杰霸霸 |
100 | 0.002 s | 8.10 MiB | C |
 席一鸣 |
100 | 0.003 s | 0.31 MiB | C++ |
 OI永别 |
100 | 0.003 s | 0.31 MiB | C++ |
 王者自由 |
100 | 0.004 s | 3.15 MiB | C++ |
 leon |
100 | 0.005 s | 13.66 MiB | C++ |
| 关于 遍历问题 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
一棵二叉树的前序遍历a1a2a3...ai和后序遍历b1b2b3...bi有一种关系：
没有兄弟节点的叶节点的根 在a序列下标为i， 在b序列下标为j 则有 a[i-1] == b[j+1] 这是因为当根只有一棵子树时，前序和后序遍历都是先遍历它的孩子，而且是唯一的一个孩子，所以相对位置是一样的。 有一个点始终过不了。。。 样例的后续遍历应该是cba。。。 退役倒计时。。。 | ||||
|
题目样例数据写错了 应该是1的！！！
Twist Fate
2016-10-10 18:52
2楼
| ||||
|
| ||||
【题目描述】
我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：
所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。
【输入格式】
输A数据共两行，第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。
【输出格式】
输出可能的中序遍历序列的总数，结果不超过长整型数。
【样例输入】
abc bca
【样例输出】
4