1127 ZigZagging on a Tree（30 分）

中序后序推出来先序遍历

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>

using namespace std;

vector<int>v1, v2;
vector<bool>visit;
int M, a;

void  DFS(int num)
{
    int numbefore = num;
    if (num == -1 || visit[num] == true)  return;

    visit[num] = true;
    auto address = find(v1.begin(), v1.end(), v2[num])-v1.begin();
    num = address;
    cout << v1[num] << " ";
    DFS(num - 1);
    DFS(numbefore - 1);
}

int main()
{
    cin >> M;
    visit.resize(M);
    for (int i = 0; i < M; i++)
    {
        cin >> a;
        v1.push_back(a);//输入第一行，中序遍历
    }
    for (int i = 0; i < M; i++)
    {
        cin >> a;
        v2.push_back(a);//输入第二行，后序遍历
    }

    DFS(M - 1);

    system("pause");
    return 0;
}

还有两个测试点没有通过

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>

using namespace std;

vector<int>v1, v2;
vector<bool>visit;
vector<vector<int>> vm(100);
int M, a;
int  dep=0;
void  DFS(int num,int depth)
{
    int numbefore = num;
    if (num == -1 || visit[num] == true)
    {
        --depth;
        return;
    }
    visit[num] = true;
    auto address = find(v1.begin(), v1.end(), v2[num])-v1.begin();
    num = address;
    //cout << v1[num] << " ";
    vm[depth].push_back(v1[num]);
    dep = max(dep, depth);
    DFS(num - 1, ++depth);
    DFS(numbefore - 1,depth);
}

void BFS()
{

}
int main()
{
    cin >> M;
    visit.resize(M);
    for (int i = 0; i < M; i++)
    {
        cin >> a;
        v1.push_back(a);//输入第一行，中序遍历
    }
    for (int i = 0; i < M; i++)
    {
        cin >> a;
        v2.push_back(a);//输入第二行，后序遍历
    }

    DFS(M - 1,0);
    //cout << endl;
    cout << vm[0][0];
    for (int i = 1; i <= dep; i++)
    {
        if (i%2==0)
        {
            reverse(vm[i].begin(), vm[i].end());
        }
        for (auto f : vm[i])
        {
            cout << " "<<f;
        }
    }
    system("pause");
    return 0;
}