首页 > 分享9.5号华为机试-二叉树最大差值
头像
tianliaoliu
发布于 2021-09-11 17:23
+ 关注

分享9.5号华为机试-二叉树最大差值

本人没有参加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的节点是最优节点

解题思路: 
机考时现场构造出二叉树是很费力的事,对解题帮助也不大,同时输入的数据也是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) 回帖
加载中...
话题 回帖