原题链接：https://vjudge.net/problem/UVA-10410 分类：树 备注：加深理解DFS和BFS, 思维
1.在BFS序中，与点a相邻的下一个点可能有三种身份：（1）节点a的孩子 （2）节点a的兄弟 （3）节点a的兄弟的孩子
2.在DFS序中，与点a相邻的下一个点可能有三种身份：（1）节点a的孩子（2）节点a的后兄弟（3）与节点a无之间关系
设bfs(x)为值为x在BFS序列中的的下标，取DFS序列中两相邻节点u,v； 若bfs(u)+1=bfs(v)并且v>u，则可将v视为u的后第一兄弟(同层要按大小关系排序)
说明：根据上面1、2点可以知道只有两种选择，若v是u的孩子，因为在BFS序列中相邻，若v不是u的兄弟，则v是u的前兄弟(优先)或者u自己的孩子，又因为v是u的孩子，u所在层只有一个节点u。因此把v视为其后兄弟，BFS和DFS的序列是不受影响的。
若bfs(u)+1=bfs(v)并且v<u，则v为u的孩子(题目说明了序列的子节点按从小到大排序)
若bfs(u)+1<bfs(v)，显然v不是u的兄弟，由于u和v在DFS序列中相邻，则v必须是u的孩子；若bfs(u)>bfs(v)，则v与u无直接关系；
因此可以不断地判断DFS中相邻两个节点的关系，若干无直接关系，说明这一条路径后续不会有继续发展，要回去找兄弟节点或者父节点，相当于把中间某些节点删去后建立新的相邻关系。所以利用了stack。
思路来源博文：https://www.cnblogs.com/npugen/p/9531912.html
代码如下：
#include<cstdio> #include<vector> #include<stack> #include<algorithm> using namespace std; const int maxn = 1000 + 5; int n, bfs[maxn]; vector<int>child[maxn]; //bfs中相邻的u,v :1、u是v的前兄弟 2、u是v的父亲 3、v是u前兄弟的儿子 //dfs中相邻的u,v :1、u是v的前兄弟 2、u是v的父亲 3、v和u无关系 int main(void) { while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); bfs[x] = i;//x在bfs序列中的位置 child[i].clear(); } stack<int>tree; int root; scanf("%d", &root); tree.push(root); for (int i = 1; i < n; i++) { int v; scanf("%d", &v); while (1) { int u = tree.top(); if (bfs[u] + 1 < bfs[v] || (bfs[u] + 1 == bfs[v] && u > v) || u == root) { child[u].push_back(v); tree.push(v); break;//找到父子关系后即找后续关系 } else tree.pop(); } } for (int i = 1; i <= n; i++) sort(child[i].begin(), child[i].end()); for (int i = 1; i <= n; i++) { printf("%d:", i); for (int j = 0; j < child[i].size(); j++) printf(" %d", child[i][j]); printf("\n"); } } return 0; }