每日OJ_牛客_Pre-Post（英文题树的遍历_排列组合）

目录

牛客_Pre-Post（英文题树的遍历_排列组合）

解析代码

---

牛客_Pre-Post（英文题树的遍历_排列组合）

---

解析代码

        这道题本质上其实是一个排列组合问题。通过前序和后序我们虽然还原不出来树，但是谁是谁的子树我们还是知道的。假设我们的前序是abejkcfghid，后序是jkebfghicda，那么我们根据前序，就能知道：

最多可以有13颗子树，也就是每一层都有13个可能位置。a是根，第一棵子树的根是b。通过后树我们能知道，b的子树有j、k、e、b共四个结点。再回到前序，向前走4个结点，下一棵子树的根是 c。以此类推，最终得到 a 为根的下一层共有 3 棵子树。

        三颗子树长这样：前序 bejk cfghi d 后序 jkeb fghic d 则这一层一共的可能性就是13个空位随便挑3个摆这3颗子树，那么有13*12*11 / 3 * 2种可能。

#include <iostream> #include <string> #include <vector> using namespace std; struct SubTree // 保存子树的前序和后序遍历结果 { SubTree(const string& pre, const string& post) : _pre(pre) , _post(post) {} string _pre; string _post; }; long long Fac(int n) // 求n的阶乘 { long long f = 1; for (int i = 1; i <= n; ++i) { f *= i; } return f; } long long CalcCom(int n, int m) // 求：C(n,m) = C(n, n-m) { m = m < (n - m) ? m : (n - m); long long r = 1; for (int i = n; i >= n - m + 1; i--) { r *= i; } return r / Fac(m); } // 找根节点的所有子树 vector<SubTree> CalcSubTree(const string& pre, const string& post) { size_t subRootPreIdx = 1; size_t postFirst = 0; // 子树在后序遍历结果中第一个元素的位置 vector<SubTree> v; while (subRootPreIdx < pre.size()) { // 确定子树的根节点 char subRoot = pre[subRootPreIdx]; // 确定根在后序遍历结果中的位置 char subRootPostIdx = post.find(subRoot); // 计算该子树中节点的个数 size_t subTreeNodeCount = subRootPostIdx - postFirst + 1; // 找到该棵子树前序遍历结果 - 找到该棵子树后序遍历结果 SubTree subTree(pre.substr(subRootPreIdx, subTreeNodeCount), post.substr(postFirst, subTreeNodeCount)); v.push_back(subTree); // 根新下一课子树根在前序遍历结果中的下标 subRootPreIdx += subTreeNodeCount; // 更新下一棵子树中第一个节点在后序遍历结果中的下标 postFirst += subTreeNodeCount; } return v; } long long CalcTreePossible(int m, const string& pre, const string& post) { // 如果树中只有1个节点---树的可能性就是唯一的 if (1 == pre.size()) return 1; // 先找出根节点的所有子树 vector<SubTree> v = CalcSubTree(pre, post); // 计算根节点子树的可能性---组合 long long result = CalcCom(m, v.size()); for (auto& e : v) result *= CalcTreePossible(m, e._pre, e._post); return result; } int main() { int m = 0; string pre, post; while (cin >> m >> pre >> post) { if (m == 0) break; cout << CalcTreePossible(m, pre, post) << endl; } return 0; }