本人没有参加9.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的节点是最优节点
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的节点是最优节点
解题思路:
机考时现场构造出二叉树是很费力的事,对解题帮助也不大,同时输入的数据也是int整数,所以想到了通过数组存储二叉树关系的方法。
将二叉树所有父-子关系都存储到一维数组中,index为偶数时永远是父节点,index+1则为其子节点。这样我们可以先遍历所有可能的结果节点,通过bfs找到他之下所有的子节点的编号,再通过编号与节点值的对应,很容易可以计算出子树的节点和。
首先计算整棵树的和:Sum,再一一尝试所有可能的节点,并子树的节点和:SubTreeSum, 则差值则为 Sum-2*SubTreeSum。
记录结果,返回其中最大的一个即可。
# include <bits/stdc++.h> using namespace std; void FindSubTree(int root, vector<int>& relation, vector<int>& storage, deque<int>& queue){ // Argument 1: root. Represents which node are we taking as an attempt // Argument 2: relation. Represents the array which stores the parent-child relation // Argument 3: storage stores all nodes of the current subtree // Arguemnt 4: queue for bfs queue.clear(); // clear queue, other wise bfs will end up infinite calls for(int i=0;i<relation.size();i++){ // traversal the relation tree if(i%2==0 && relation[i]==root){ // if the position is an even number, which means it is a node with child // and its value equals to the root we are attempting queue.push_back(relation[i+1]); storage.push_back(relation[i+1]); // both queue and storage needs to store its child node which must be relation[i+1] } } for(int pos:queue){ // after traversal we now have a queue of its child nodes, // for example node 0 has childs {1, 3} FindSubTree(pos,relation,storage,queue); // find the child nodes of these child nodes } } int main () { int n; cin>>n; // n represents the number of treenodes; int sum; vector<int> value(n,0); for(int i=0;i<n;i++){ cin>>value[i]; sum += value[i]; } // value array to store the node's value // in relation to its index, value[0]=4 equavilent to Node 0:4. // at the meantime, calculate the sum value of the entire tree vector<int> tree; int node; while(cin>>node && node != 99) tree.push_back(node); // use array Tree{...} to store the parent-child relation vector<int> storage; // initialize subtree nodes index array deque<int> queue; // initialize queue for bfs search int res[2] = {0,0}; int maxdiff = 0; // store result and maximum differences for(int i=1;i<n;i++){ // traversal all treenode idex except root storage.clear(); // update the sub-tree-nodes array everytime start a new attempt int SubTreeSum = 0; storage.push_back(i); // root need to be count in the subtree as well FindSubTree(i,tree,storage,queue); // bfs to get all subtree node index for(int pos:storage) SubTreeSum += value[pos]; // count the sum of all subtree nodes int diff = abs(sum-2*SubTreeSum); // count the temperary differences between the subtree and the rest of the tree if (diff>maxdiff){ maxdiff = diff; res[0] = i, res[1] = maxdiff; } // if the differences is greater than before, store that result } cout<<res[0]<<" "<<res[1]<<endl; return 0; }
全部评论
(0) 回帖