题目

代码

#include<bits/stdc++.h>
using namespace std;const int N = 40;int in[N], pos[N]; //中序、后序
int idx[N]; //中序的值->索引
unordered_map<int, int> l, r; //根节点的左、右树根节点
int n;
int build(int il, int ir, int pl, int pr)
{int root = pos[pr];int k = idx[root];if(il < k) l[root] = build(il, k-1, pl, pl + k - 1 - il);if(k < ir) r[root] = build(k+1, ir, pl + k - 1 - il + 1, pr-1);return root;
} 
void bfs(int root)
{queue<int> q;q.push(root);while(!q.empty()){int fr = q.front();cout << fr << " ";q.pop();if(l.count(fr)) q.push(l[fr]);if(r.count(fr)) q.push(r[fr]);}
}
int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> pos[i];for(int i = 1; i <= n; i++) cin >> in[i], idx[in[i]] = i;int root = build(1, n, 1, n);bfs(root);return 0;
}

思考

对于树的遍历，算法应设计如下

层序：bfs（queue）

先序：dfs(递归)  (先输出)    or dfs(stack)（不论先后输出）

中序：dfs(递归)（中间输出）

后序：dfs(递归)（后面输出）

理解

queue+先左再右就可以保证同一层中从左到右，不同层之间从上到下。

根据序列遍历的要求，要先左根再右根。所以递归要先左再右。

但是用stack模拟要反着来，先压入右节点，再压入左节点。然后左节点出又是如此，这样就像上面那个先左再右，右生左继续先左再右了。

提一个问题：为什么递归中改变输出的时机可以在不同序列间切换，但是在stack中不行？

答：递归中的子递归也有输出操作，从代码上看，就像左子输出、右子输出和根节点输出在排序一样；而stack中的输出就是当前top节点的值（不是递归，没有子输出），于是输出顺序和访问顺序相同，是定死的先序。要改变序列，必须从访问顺序上下手

补充

（递归,先中后序列）

void firsto(int root)
{cout << root << " ";if(l.count(root)) firsto(l[root]);if(r.count(root)) firsto(r[root]);
}
void ino(int root)
{if(l.count(root)) ino(l[root]);cout << root << " ";if(r.count(root)) ino(r[root]);
}
void poso(int root)
{if(l.count(root)) poso(l[root]);if(r.count(root)) poso(r[root]);cout << root << " ";
}

（stack，先序）

void first_dfs(int root)
{stack<int> s;s.push(root);while(!s.empty()){int fr = s.top();cout << fr << " ";s.pop();if(r.count(fr)) s.push(r[fr]);if(l.count(fr)) s.push(l[fr]);}
}