一道十分简单的模拟加递归

题目描述

给出一棵二叉树的中序与后序排列。

求出它的先序排列。

约定树结点用不同的大写字母表示.

样例

BADC BDCA

ABCD

算法

(模拟加递归) $O(n)$

直接通过后序遍历分左右，分别递归左右子树。

时间复杂度

一共要把所有节点遍历一遍，总共的时间复杂度是$O(n)$

参考文献

AcWing 5498. 求先序排列

C++ 代码

#include <iostream>

using namespace std;

void dfs(string a, string b)
{
    if (b.empty()) return;

    printf("%c", b.back());
    int t = a.find(b.back());

    dfs(a.substr(0, t), b.substr(0, t));
    dfs(a.substr(t + 1), b.substr(t, b.size() - 1 - t));
}

int main()
{
    string a, b;
    cin >> a >> b;
    dfs(a, b);
    return 0;
}