9.8华为机考第一题

通过95%，忽略复杂度😂

请大佬赏脸看一下，没过的5%是因为什么？

【问题】

给出一颗二叉树，每个节点有一个编号和一个值，该值可能为负数，请你找出一个最优节点(除根节点外)，使得在该节点将树分成两棵树后(原来的树移除这个节点及其子节点，新的树以该节点为根节点)，分成的两棵树各节点的和之间的差绝对值最大。请输出该节点编号，如有多个相同的差，输出编号最小的节点。

【输入】

4 9 -7 -8

0 1

0 3

1 2

第一行，四个节点，编号0-3，范围为1-10000
第二行，节点0-3的权值

第三行到第五行，表示二叉树各节点间的父子关系
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;
}

#华为机试##笔试题目##华为#