算法:树的遍历
时间复杂度:$O(N)$
依据中序遍历和前序遍历求后序遍历,这类题在 LeetCode 上应该是非常常见的。
如下图:
先用哈希表记录中序遍历中每个字母的位置,以便在递归时能准确知道根节点在中序遍历中的位置,然后分别递归中序遍历的左子树、前序遍历的左子树 和 中序遍历的右子树、前序遍历的右子树,以保证所得到的序列是后序遍历的结果。
具体参数如下:
$[il, k - 1]$、 $[pl + 1, pl + 1 + k - 1 - il]$
$[k + 1, ir]$、$[pl + 1 + k - 1 - il + 1, pr]$
其中 $k$ 表示中序遍历根节点的位置。
C++ 代码
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
int n;
unordered_map <char, int> pos;
string preorder, inorder, postorder;
void build(int il, int ir, int pl, int pr)
{
if (il > ir) return ;
int k = pos[preorder[pl]];
build(il, k - 1, pl + 1, pl + 1 + k - 1 - il); // 左
build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr); // 右
postorder += preorder[pl]; // 左 -> 右 -> 根
}
int main()
{
cin >> inorder >> preorder;
n = inorder.size();
for (int i = 0; i < n; ++i) pos[inorder[i]] = i;
build(0, n - 1, 0, n - 1);
cout << postorder << endl;
return 0;
}