9.8华为机考第一题
通过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; }