一、题意

第一行一个n表示一棵树有n个结点。
然后第二三行分别给出这棵树的bfs和dfs序列。（子节点中会先遍历编号小的）
要求输出每个节点的子节点有哪些。

二、解析

这题比较难。最终做法是，使用栈来模拟dfs的过程。在输入dfs序列时，同时维护一个栈，当在树上递归时则往栈中加入该节点，当发生了回溯时，则需要从栈中排出结点。bfs序列实际上我们可以从中提取出结点的pos数组（即结点在层次遍历中的下标）。利用这个pos数组，在dfs发生递归时，除了第一层外，当前结点的pos应该大于上一结点的pos+1（这样才会是往下走的dfs，并且不是兄弟结点）；当发生回溯时，当前节点的pos应该小于等于上一结点的pos+1（这样才说明dfs已经遍历完一棵子树，所以结点pos往回跳了，所以才变小了，相等时表示是兄弟节点）。利用这一特点，在递归发生时，当前节点和上一结点就是父子关系，记录到ans中即可。

三、代码

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int maxn = 1000 + 5;
int n, pos[maxn];
vector<int> ans[maxn];

int main() {
    while(cin >> n) {
        for(int i = 1; i <= n; i ++) ans[i].clear();
        for(int i = 0, x; i < n; i ++) {
            cin >> x;
            pos[x] = i;
        }
        stack<int> stk;
        for(int i = 0, x; i < n; i ++) {
            cin >> x;
            while(!stk.empty() && i >= 2 && pos[x] <= pos[stk.top()] + 1) stk.pop();
            if(!stk.empty()) ans[stk.top()].push_back(x);
            stk.push(x);
        }
        for(int i = 1; i <= n; i ++) {
            cout << i << ":";
            for(int child : ans[i]) cout << " " << child;
            cout << endl;
        }
    }
}

四、归纳

  • 难题的话还是要靠多刷题积累经验了