【二叉树】求二叉树先序与后序的题目及方法【二叉树】求二叉树先序与后

前言对于一颗二叉树，我们如果知道了它的中序和后序，就可以求出它的先序；同样的，我们如果知道了它的中序和先序，也可以求出它的后序；但是注意，知道先序和后序是不能求出唯一中序的。
在求后序前，我们可以先学习一下如何求先序，因为求先序比较好理解；
求先序题目：[P1030 NOIP2001 普及组] 求先序排列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
因为先序遍历为根左右，中序为左根右，后序为左右根
因此每一个后序的最后一个字母都是根节点，知道了根节点后就可以在中序里求出左边的树和右边的树，放进函数里递归即可求出先序！
注意在代码中用到了substr()函数，它的作用是在原字符串中截取一段字符串出来，原函数不变，其用法如下：
1.当传入两个参数时，即substr(a,b),此时a为截取起始点，b为截取长度；
2.当只传入一个参数时，即substr(a),此时a为截取起始点，并且截取至字符串末尾。
代码

#include #include using namespace std; typedef long long ll; void go(string mid, string aft) { if (mid.size() > 0) { char t = aft[aft.size() - 1]; cout << t; //因为先序的第一个字母为根节点，因此直接先输出后序的最后一个字母 int pos = mid.find(t); go(mid.substr(0, pos), aft.substr(0, pos)); go(mid.substr(pos + 1), aft.substr(pos, aft.size() - 1 - pos)); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); string mid, after; cin >> mid >> after; go(mid, after); return 0; }

求后序题目：[P1827 USACO3.4]美国血统 American Heritage - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
【【二叉树】求二叉树先序与后序的题目及方法】求后序的方法与求先序基本一样，但因为后序的最后一个字母才是根，于是在输出时要最后输出最大的根，即在递归返回时输出字符。
代码

#include #include using namespace std; typedef long long ll; void tree(string pre, string in) { if (pre.empty()) return; int pos = in.find(pre[0]); tree(pre.substr(1, pos), in.substr(0, pos)); tree(pre.substr(pos + 1), in.substr(pos + 1)); cout << pre[0]; //在递归返回时才输出！！ } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); string a, b; cin >> a >> b; tree(b, a); return 0; }