华为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;
        }
    }
全部评论

相关推荐

one_t:硕还是本?什么岗
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务