9.8华为机考第一题

通过95%,忽略复杂度😂
请大佬赏脸看一下,没过的5%是因为什么?
【问题】
给出一颗二叉树,每个节点有一个编号和一个值,该值可能为负数,请你找出一个最优节点(除根节点外),使得在该节点将树分成两棵树后(原来的树移除这个节点及其子节点,新的树以该节点为根节点),分成的两棵树各 节点的和之间的差绝对值最大。请输出该节点编号,如有多个相同的差,输出编号最小的节点。
【输入】
4
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;
}




#华为机试##笔试题目##华为#
全部评论
怎么确定二叉树的根节点呀,还是说默认的0号结点是根节点
1 回复 分享
发布于 2021-09-08 23:10
我也是95%,不过是java写的
点赞 回复 分享
发布于 2021-09-08 23:05
最后几行,通过value确定node肯定有问题啊😂
点赞 回复 分享
发布于 2021-09-08 23:05
先sum 所有权值然后遍历每一个子节点,求子节点产生树的的权值的和,记录每一次的查与差的最大值比较,最后返回差最大的子节点的索引
点赞 回复 分享
发布于 2021-09-10 11:11

相关推荐

11-01 20:03
已编辑
门头沟学院 算法工程师
Amazarashi66:这种也是幸存者偏差了,拿不到这个价的才是大多数
点赞 评论 收藏
分享
大拿老师:这个简历,连手机号码和照片都没打码,那为什么关键要素求职职位就不写呢? 从上往下看,都没看出自己到底是产品经理的简历,还是电子硬件的简历? 这是一个大问题,当然,更大的问题是实习经历的描述是不对的 不要只是去写实习流程,陈平,怎么去开会?怎么去讨论? 面试问的是你的产品功能点,是怎么设计的?也就是要写项目的亮点,有什么功能?这个功能有什么难处?怎么去解决的? 实习流程大家都一样,没什么优势,也没有提问点,没有提问,你就不得分 另外,你要明确你投的是什么职位,如果投的是产品职位,你的项目经历写的全都是跟产品无关的,那你的简历就没用 你的面试官必然是一个资深的产品经理,他不会去问那些计算机类的编程项目 所以这种四不像的简历,在校招是大忌
点赞 评论 收藏
分享
2 22 评论
分享
牛客网
牛客企业服务