A27924. 树的偏斜度对于一棵二叉树，令 nL 表示仅有左孩子的结点的个数，令 nR 表示仅有右孩子的结点的个数。这棵树的“偏斜度”定义为 Ds = nL - nR。本题就请你计算任一棵给定二叉树的 Ds。输入输入在第一行给出正整数 n (≤ 103)，为二叉树中结点个数。随后两行先后给出这棵树的后序遍历和中序遍历序列，键值为 1 到 n 的整数。同行数字间以空格分隔。输出在一行中按以下格式输出树的偏斜度：…
填空题
困难
知识点
题目描述
树的偏斜度
对于一棵二叉树，令 nL 表示仅有左孩子的结点的个数，令 nR 表示仅有右孩子的结点的个数。这棵树的“偏斜度”定义为 Ds = nL - nR。本题就请你计算任一棵给定二叉树的 Ds。
输入
输入在第一行给出正整数 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参考答案
//参考代码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;
}
上一题
下一题