【HackerRank】Cut the tree

时间:2023-02-01 07:29:29

题目链接:Cut the tree

题解:题目要求求一条边,去掉这条边后得到的两棵树的节点和差的绝对值最小。

暴力求解会超时。

如果我们可以求出以每个节点为根的子树的节点之和,那么当我们去掉一条边(a,b)的时候,其中的一棵树必是以a或者b为根的子树,那么我们就可以知道生成的两棵树的节点之和了。所以,当我们得到以每个节点为根的子树节点和这个信息后(把这个信息存储在TreeNode的value变量中),通过遍历每个节点(每个节点为根的子树必然为某次cut得到的子树之一,例如下图中,2为根的子树对应切割边(1,2)得到的树,而5为根的子树对应切割边(1,5)得到的树),求出最小的W-2*root.value即为所求(W是所有节点的值得和)。

【HackerRank】Cut the tree

树节点的数据结构定义如下:

static class TreeNode{
int value;
int number;
ArrayList<TreeNode> children;
public TreeNode(int value,int number){
this.value = value;
this.number = number;
children = new ArrayList<TreeNode>();
}
}

value表示该顶点对应的值,number表示顶点的编号,children表示子节点的列表(这里指表示连接关系,也有可能children里面其实存放了父节点,不过可以用接下来的visited数组避免访问到父节点)。

然后从树的任意一个节点开始dfs,把它的value值依次加上各个child为root的子树节点值,就得到以它为root的子树的节点值得和了。而它的child为root的子树节点和就用递归的方法求。上面说了,每次读入一条边(a,b)的时候,即把b加入到a的children集合里面,也把a加入到b的children集合里面。那么在dfs的时候,怎么知道谁是父节点,谁是子节点呢?就用一个visited数组,因为在dfs过程中,父节点一定先被访问,所以在一个节点的children集合里面,已经被visited过的节点就不是它的子节点了。

最后代码如下:

 import java.util.*;

 public class Solution {
static class TreeNode{
int value;
int number;
ArrayList<TreeNode> children;
public TreeNode(int value,int number){
this.value = value;
this.number = number;
children = new ArrayList<TreeNode>();
}
} private static int dfs(TreeNode root,boolean[] visited){
visited[root.number]=true;
for(TreeNode child:root.children){
if(!visited[child.number]){
root.value += dfs(child, visited);
}
}
return root.value;
} public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
TreeNode[] treeNodes = new TreeNode[n];
int W = 0; for(int i = 0;i < n;i++)
{
int value = in.nextInt();
treeNodes[i]=new TreeNode(value,i);
W += value;
} for(int i = 0;i < n-1;i++){
int a = in.nextInt();
int b = in.nextInt();
treeNodes[a-1].children.add(treeNodes[b-1]);
treeNodes[b-1].children.add(treeNodes[a-1]);
} boolean[] visited = new boolean[n]; dfs(treeNodes[0], visited);
int miniDif = Integer.MAX_VALUE; for(TreeNode t:treeNodes){
miniDif = Math.min(miniDif, Math.abs(W-2*t.value));
} System.out.println(miniDif); }
}

另外要积累的一点是java中nested class和inner class的区别,见*上面的详细解答,所以上述代码中第4行要把TreeNode声明为nested class,否则它只能通过类Solution调用。

【HackerRank】Cut the tree的更多相关文章

  1. 【数据结构】B-Tree&comma; B&plus;Tree&comma; B&ast;树介绍 转

    [数据结构]B-Tree, B+Tree, B*树介绍 [摘要] 最近在看Mysql的存储引擎中索引的优化,神马是索引,支持啥索引.全是浮云,目前Mysql的MyISAM和InnoDB都支持B-Tre ...

  2. 【题解】Cut the Sequence&lpar;贪心区间覆盖&rpar;

    [题解]Cut the Sequence(贪心区间覆盖) POJ - 3017 题意: 给定一大堆线段,问用这些线段覆盖一个连续区间1-x的最小使用线段的数量. 题解 考虑一个这样的贪心: 先按照左端 ...

  3. 【LeetCode】199&period; Binary Tree Right Side View 解题报告(Python)

    [LeetCode]199. Binary Tree Right Side View 解题报告(Python) 标签: LeetCode 题目地址:https://leetcode.com/probl ...

  4. 【数据结构】B-Tree&comma; B&plus;Tree&comma; B&ast;树介绍

    [摘要] 最近在看Mysql的存储引擎中索引的优化,神马是索引,支持啥索引.全是浮云,目前Mysql的MyISAM和InnoDB都支持B-Tree索引,InnoDB还支持B+Tree索引,Memory ...

  5. 【LeetCode】Balanced Binary Tree 解题报告

    [题目] Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced bi ...

  6. 【LeetCode】145&period; Binary Tree Postorder Traversal

    Difficulty: Hard  More:[目录]LeetCode Java实现 Description https://leetcode.com/problems/binary-tree-pos ...

  7. 【HackerRank】Utopian tree

    The Utopian tree goes through 2 cycles of growth every year. The first growth cycle of the tree occu ...

  8. 【BZOJ-4353】Play with tree 树链剖分

    4353: Play with tree Time Limit: 20 Sec  Memory Limit: 256 MBSubmit: 31  Solved: 19[Submit][Status][ ...

  9. 【leetcode】Binary Search Tree Iterator(middle)

    Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the ro ...

随机推荐

  1. jasperreports&plus;iReport制作报表笔记

    一. 准备工作 1. 下载相关工具:点击此下载相关工具,jasperreports-5.6.0-project.zip中有提供所需的jar包. 二. 安装ant 1. 解压apache-ant-1.9 ...

  2. 实战录&&num;160&semi;&vert; Redis的主从服务器搭建

    <实战录>导语 云端卫士<实战录>栏目定期会向粉丝朋友们分享一些在开发运维中的经验和技巧,希望对于关注我们的朋友有所裨益.本期分享人为云端卫士安全平台工程师田全磊,将带来Red ...

  3. BI之SSAS完整实战教程3 -- 创建第一个多维数据集

    上一篇我们已经完成了数据源的准备工作,现在我们就开始动手,创建第一个多维数据集(Cube). 文章提纲 使用多维数据集向导创建多维数据集 总结Cube设计器简介 维度细化 总结 一.使用向导创建多维数 ...

  4. &lbrack;转帖&rsqb; CvMat,Mat和IplImage之间的转化和拷贝

    原文地址: http://blog.csdn.net/holybin/article/details/17711013 在OpenCV中Mat.CvMat和IplImage类型都可以代表和显示图像. ...

  5. mysql笔记(前面自己写的不标准有些地方)

    day15-MySQL 数据库 1 数据库概念(了解) 1.1 什么是数据库 数据库就是用来存储和管理数据的仓库! 数据库存储数据的优先: l  可存储大量数据: l  方便检索: l  保持数据的一 ...

  6. IIS7&period;0配置HTTPS安全类型的网站

    HTTPS,它是一个安全通信通道,是基于HTTP开发,用于在客户计算机和服务器之间交换信息.它使用安全套接字 层(SSL)进行信息交换,简单来说它是HTTP的安全版.主要在一些对安全性要求比较高的网站 ...

  7. android5&period;0问题

    2042-2247/system_process W/AudioTrack﹕ AUDIO_OUTPUT_FLAG_FAST denied by client libzte-ril.so has tex ...

  8. iOS&lowbar;22自定义键盘工具栏

    最后效果图: Main.storyboard KeyboardTool.xib watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcHJlX2VtaW5lbnQ ...

  9. while循环写3次用户名密码验证程序

    #变量来自原始用户名和密码 username = 'admin' password = 'nimda' #变量来自计数器 count = 0 #循环条件计数器小于3,则执行while代码块 while ...

  10. java8的函数式接口

    函数式接口 就是在java8里允许你为一个接口(只有一个实现的,声明为FunctionalInterface注解的)实现一个匿名的对象,大叔感觉它与.net平台的委托很类似,一个方法里允许你接收一个方 ...