华为OD机试真题 - 最富裕的小家庭
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = Integer.parseInt(in.nextLine());
String str = in.nextLine();
int[] assets = Arrays.stream(str.split(" ")).mapToInt(Integer::parseInt).toArray();
int[][] map = new int[num - 1][2];
for (int i = 0; i < num - 1; i++) {
map[i] = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
Node head = buildTree(map, assets);
// printTree(head);
System.out.println(getMaxFamlie(head));
}
public static int getMaxFamlie(Node head) {
if (head == null)
return 0;
int max = 0;
max += head.value;
if (head.left != null)
max += head.left.value;
if (head.right != null)
max += head.right.value;
max = Math.max(getMaxFamlie(head.left), max);
max = Math.max(getMaxFamlie(head.right), max);
return max;
}
public static Node buildTree(int[][] map, int[] assets) {
int count = 0;
Node[] nodes = new Node[assets.length];
for (int i = 0; i < assets.length; i++) {
nodes[i] = new Node(assets[i]);
}
for (int i = 0; i < map.length; i++) {
if (nodes[map[i][0] - 1].left == null)
nodes[map[i][0] - 1].left = nodes[map[i][1] - 1];
else nodes[map[i][0] - 1].right = nodes[map[i][1] - 1];
}
return nodes[0];
}
public static void printTree(Node head) {
if (head == null)
return;
System.out.println(head.value);
printTree(head.left);
printTree(head.right);
}
static class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
}
Scanner in = new Scanner(System.in);
int num = Integer.parseInt(in.nextLine());
String str = in.nextLine();
int[] assets = Arrays.stream(str.split(" ")).mapToInt(Integer::parseInt).toArray();
int[][] map = new int[num - 1][2];
for (int i = 0; i < num - 1; i++) {
map[i] = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
Node head = buildTree(map, assets);
// printTree(head);
System.out.println(getMaxFamlie(head));
}
public static int getMaxFamlie(Node head) {
if (head == null)
return 0;
int max = 0;
max += head.value;
if (head.left != null)
max += head.left.value;
if (head.right != null)
max += head.right.value;
max = Math.max(getMaxFamlie(head.left), max);
max = Math.max(getMaxFamlie(head.right), max);
return max;
}
public static Node buildTree(int[][] map, int[] assets) {
int count = 0;
Node[] nodes = new Node[assets.length];
for (int i = 0; i < assets.length; i++) {
nodes[i] = new Node(assets[i]);
}
for (int i = 0; i < map.length; i++) {
if (nodes[map[i][0] - 1].left == null)
nodes[map[i][0] - 1].left = nodes[map[i][1] - 1];
else nodes[map[i][0] - 1].right = nodes[map[i][1] - 1];
}
return nodes[0];
}
public static void printTree(Node head) {
if (head == null)
return;
System.out.println(head.value);
printTree(head.left);
printTree(head.right);
}
static class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
}
全部评论
相关推荐
//鲨鱼辣椒:什么什么都作废了,如同一场大雪覆盖了前半生的荒唐
点赞 评论 收藏
分享