简答题
偏难
#13200
树的偏斜度 对于一棵二叉树,令 nL 表示仅有左孩子的结点的个数,令 nR 表示仅有右孩子的结点的个数。这棵树的“偏斜度”定义为 Ds = nL - nR。本题…
树的偏斜度
对于一棵二叉树,令 nL 表示仅有左孩子的结点的个数,令 nR 表示仅有右孩子的结点的个数。这棵树的“偏斜度”定义为 Ds = nL - nR。本题就请你计算任一棵给定二叉树的 Ds。
时间限制:1000
内存限制:65536
输入
输入在第一行给出正整数 n (≤ 103),为二叉树中结点个数。随后两行先后给出这棵树的后序遍历和中序遍历序列,键值为 1 到 n 的整数。同行数字间以空格分隔。
输出
在一行中按以下格式输出树的偏斜度: Ds = nL - nR
样例输入
7 1 2 7 5 4 3 6 1 2 3 4 7 5 6
样例输出
2 = 3 - 1
答案与解析
正确答案:<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>
这道题暂未补解析。