通过95%，忽略复杂度😂
请大佬赏脸看一下，没过的5%是因为什么？
【问题】
给出一颗二叉树，每个节点有一个编号和一个值，该值可能为负数，请你找出一个最优节点(除根节点外)，使得在该节点将树分成两棵树后(原来的树移除这个节点及其子节点，新的树以该节点为根节点)，分成的两棵树各 节点的和之间的差绝对值最大。请输出该节点编号，如有多个相同的差，输出编号最小的节点。
【输入】
4
4 9 -7 -8
0 1
0 3
1 2
第一行，四个节点，编号0-3，范围为1-10000
第二行，节点0-3的权值
第二行，节点0-3的权值
第三行到第五行，表示二叉树各节点间的父子关系
0 1 // 节点0的左节点是1
0 3 // 节点0的右节点是3
1 2 // 节点1的左节点是2
注意:左节点永远出现在右节点之前
0:4
0 1 // 节点0的左节点是1
0 3 // 节点0的右节点是3
1 2 // 节点1的左节点是2
注意:左节点永远出现在右节点之前
0:4
/ \
1:9 3:-8
/
2:-7
【输出】
节点编号，示例中编号为3的节点是最优节点 #include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode():val(0),left(nullptr),right(nullptr){}
TreeNode(int _val):val(_val), left(nullptr), right(nullptr) {}
};
int MaxofAbs_val = 0; // 两树节点和的差值绝对值 的最大值
int sum0 = 0; // 原树所有节点和
TreeNode* res = nullptr;// 结果节点
int SumofTree(TreeNode* node) {
if(node == nullptr) return 0;
return node->val+ SumofTree(node->left)+SumofTree(node->right);
}
void compare(TreeNode* node) {
if (node == nullptr)return;
// cout <<">>":" <<node->val << endl;
int newtree_sum = SumofTree(node);
int oldtree_sum = sum0 - newtree_sum;
// cout << "newtree_sum " << newtree_sum << " , " << "oldtree_sum" << oldtree_sum << endl;
if (MaxofAbs_val < abs(newtree_sum - oldtree_sum)) {
MaxofAbs_val = abs(newtree_sum - oldtree_sum);
res = node;
}
// cout << "abs(newtree_sum - oldtree_sum)" << abs(newtree_sum - oldtree_sum) << endl;
compare(node->left);
compare(node->right);
}
void qianxubianli(TreeNode* head) {
if (head == nullptr)return;
compare(head->left);
compare(head->right);
}
int main() {
int n; // 节点个数
cin >> n;
vector<int> arr_val(n, 0); // 节点权值
vector<TreeNode*> arr_ptr; // 节点指针
for (int i = 0; i < n; i++) {
cin >> arr_val[i];
TreeNode* node = new TreeNode(arr_val[i]);
arr_ptr.push_back(node);
sum0 += arr_val[i];
}
vector<vector<int> > arr_rel(n-1, vector<int>(2,0));// 除去根节点
// 建树
cin >> arr_rel[0][0] >> arr_rel[0][1];
arr_ptr[arr_rel[0][0]]->left = arr_ptr[arr_rel[0][1]];
for (int i = 1; i < n - 1; i++) {
cin >> arr_rel[i][0] >> arr_rel[i][1];
if (arr_rel[i][0] == arr_rel[i - 1][0]) {
arr_ptr[arr_rel[i][0]]->right = arr_ptr[arr_rel[i][1]];
}
else
{
arr_ptr[arr_rel[i][0]]->left = arr_ptr[arr_rel[i][1]];
}
}
// 前序遍历二叉树并比较差值绝对值大小
qianxubianli(arr_ptr[0]);
for (int i = 0; i < n; i++) {
if (res->val == arr_val[i]) {
cout << i;
break;
}
}
return 0;
} 
全部评论
(4) 回帖