答案:<pre class="brush:cpp;toolbar:false">//参考代码1
#include <iostream>
#include <vector>
using namespace std;
pair<int, int> calcSkew(vector<int>& post, vector<int>& in, int ps, int pe, int is, int ie) {
if (ps > pe) return {0, 0};
int root = post[pe], idx = is;
while (in[idx] != root) idx++;
pair<int, int> left = calcSkew(post, in, ps, ps + idx - is - 1, is, idx - 1);
pair<int, int> right = calcSkew(post, in, ps + idx - is, pe - 1, idx + 1, ie);
return {left.first + right.first + (idx > is && idx == ie), left.second + right.second + (idx < ie && idx == is)};
}
int main() {
int n;
cin >> n;
vector<int> post(n), in(n);
for (int &x : post) cin >> x;
for (int &x : in) cin >> x;
pair<int, int> res = calcSkew(post, in, 0, n - 1, 0, n - 1);
cout << res.first - res.second << " = " << res.first << " - " << res.second << endl;
}</pre><pre class="brush:cpp;toolbar:false">//参考代码2
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd, unordered_map<int, int>& inMap) {
if (inStart > inEnd || postStart > postEnd) return nullptr;
int rootVal = postorder[postEnd];
TreeNode* root = new TreeNode(rootVal);
int rootIndex = inMap[rootVal];
int leftSize = rootIndex - inStart;
root->left = buildTree(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSize - 1, inMap);
root->right = buildTree(inorder, postorder, rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1, inMap);
return root;
}
void countSkew(TreeNode* node, int& nL, int& nR) {
if (!node) return;
bool hasLeft = node->left != nullptr;
bool hasRight = node->right != nullptr;
if (hasLeft && !hasRight) nL++;
else if (!hasLeft && hasRight) nR++;
countSkew(node->left, nL, nR);
countSkew(node->right, nL, nR);
}
int main() {
int n;
cin >> n;
vector<int> post(n), in(n);
for (int i = 0; i < n; i++) cin >> post[i];
for (int i = 0; i < n; i++) cin >> in[i];
unordered_map<int, int> inMap;
for (int i = 0; i < n; i++) inMap[in[i]] = i;
TreeNode* root = buildTree(in, post, 0, n-1, 0, n-1, inMap);
int nL = 0, nR = 0;
countSkew(root, nL, nR);
cout << nL - nR << " = " << nL << " - " << nR << endl;
return 0;
}</pre><p><br/></p>
这道题暂未补解析。