全部评论
这个要求树的重心吧
设节点数为n,时间复杂度为On空间复杂度为On的解法。先遍历一遍树,用map存储节点对应的树的节点数量。然后从根开始,设left为左子树的节点数量,设right右子树的节点数量。r若left-right的绝对值<=1,那么该结点就是最优节点。否则,若left大往左走,right大往右走。然后更新对应的left值和right 值循环即可。(循环进行时left与right不再表示左子树的节点数量和右子树的节点数量)
统计各个节点子树的大小。然后先算根节点的代价,然后其他点的时候根据靠近的点,远离的点的数量,转移一下就可以了。
相关推荐
程序员花海_:实习写的看起来像项目了
点赞 评论 收藏
分享
10-19 12:41
成都工业学院 嵌入式软件开发
嵌入式的小白:简历关键的就是项目经历,你这密密麻麻的,我一点开就不想看了,每一条都不换行,而且每一个里面写那么多,需要精简一下,这样别人看一眼就能知道你做了啥,用了啥技术 点赞 评论 收藏
分享
点赞 评论 收藏
分享
