题目
给出一棵二叉树的前序和中序遍历的结果，还原这棵二叉树并输出其后序遍历的结果。
具体描述请见hihoCoder。
解题思路
经典问题。假设二叉树形如：
其前序为ABDEGHCFIJ，中序为'DBGEHACIJF'，后序为DGHEBJIFCA。由于前序遍历是根节点+左子树+右子树，中序遍历是左子树+根节点+右子树，因此A是根节点，且BDEGH是左子树的前序，CFIJ是左子树的中序，DBGEH为左子树的中序，CIJF为右子树的中序。此时我们可以发现后序即为左子树+右子树+根节点，即A一定是当前后序中最后的节点。因此可以递归的求出后序。
时间复杂度
时间复杂度为N。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <iostream>
#include <string>
using namespace std;
string postOrder(string preOrder, string inOrder) {
int len = preOrder.size();
if (len == 0)
return "";
int idx = 0;
for (; idx < len; idx++)
if (inOrder[idx] == preOrder[0])
break;
return postOrder(preOrder.substr(1, idx), inOrder.substr(0, idx)) +
postOrder(preOrder.substr(idx + 1, len - idx - 1),
inOrder.substr(idx + 1, len - idx - 1)) + preOrder[0];
}
int main() {
string preOrder, inOrder;
cin >> preOrder >> inOrder;
cout << postOrder(preOrder, inOrder);
return 0;
}
|
