Данный родительский массив и массив значений.Найти наилучшую сумму в дереве

Question

Данный родительский массив такой, что parent [i] = j, где j - родительский массив и массив значений.Необходимо найти наилучшую возможную сумму.

Корневой узел будет иметь значение -1 в качестве родителя.

Максимально возможная сумма - это максимальная сумма в одном из путей дерева.

Ex)

 Integer[] parent = new Integer[] { -1, 0, 0, 2, 3 };
 Integer[] values = new Integer[] { 0, 4, 6, -11, 3 };

     (0/0)----(1/4)
     |
     |
     (2/6)
     |
     |
     (3/-11)
     |
     |
     (4/3)

Максимальная сумма здесь будет 6 + 0 + 4 = 10 для пути 2 -> 0 -> 1.

Я попытался решить это способом dfs.Но не уверен, что это работает для всех случаев.Ниже мой код.Это дает всю возможную сумму.мы можем вывести из этого максимум.

    package com.programs.algo;

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.stream.Collectors;

    public class BestPossibleSum {

        static class Node<T> {

        T label;
        T data;
        List<Node<T>> nodes;
       }

public static void main(String[] args) {

    Integer[] parent = new Integer[] { -1, 0, 0, 1, 1, 3, 5 };
    Integer[] values = new Integer[] { 0, 4, 6, -11, 3, 10, 11 };

    List<Integer> list1 = new ArrayList<>(Arrays.asList(parent));
    List<Integer> list2 = new ArrayList<>(Arrays.asList(values));
    bestPossibleSum(list1, list2);
}

static List<Node<Integer>> tree = new ArrayList<>();

private static void bestPossibleSum(List<Integer> list1, List<Integer> list2) {
    int adj[][] = new int[list1.size()][list1.size()];
    createTree(list1, list2, adj);
    List<Integer> traversedNodes = new ArrayList<>();
    List<Integer> sumOfraversedNodes = new ArrayList<>();

    for (int i = 0; i < adj.length; i++) {
        dfs(tree.get(i), traversedNodes, sumOfraversedNodes);
        traversedNodes.clear();
    }

    System.out.println(sumOfraversedNodes);
}

private static void dfs(Node<Integer> tree, List<Integer> traversedNodes, List<Integer> sums) {
    if (!traversedNodes.contains(tree.label)) {
        traversedNodes.add(tree.label);
        sums.add(getSum(traversedNodes));
        for (Node<Integer> child : tree.nodes) {
            dfs(child, traversedNodes, sums);
        }
    }
}

private static Integer getSum(List<Integer> traversedNodes) {
    System.out.println(traversedNodes);
    return traversedNodes.stream().reduce(0, Integer::sum);
}

private static void createTree(List<Integer> parent, List<Integer> values, int[][] adj) {

    for (int i = 0; i < parent.size(); i++) {
        Node<Integer> node = new Node<>();
        node.label = i;
        node.data = values.get(i);
        node.nodes = new ArrayList<>();
        tree.add(i, node);
    }

    for (int i = 0; i < parent.size(); i++) {
        if (parent.get(i) != -1) {
            adj[parent.get(i)][i] = 1;
            adj[i][parent.get(i)] = 1;
            tree.get(parent.get(i)).nodes.add(tree.get(i));
        }
    }

    tree.forEach(t -> {
        System.out.println(t.label);
        System.out.println(t.nodes.stream().map(m -> m.label).collect(Collectors.toList()));
    });
    // System.out.println(Arrays.deepToString(adj));
}

}

Answer 1

Публикация кода Java, рассматривающего его как дерево с левым и правым узлами.

https://www.geeksforgeeks.org/construct-a-binary-tree-from-parent-array-representation/

https://www.geeksforgeeks.org/find-maximum-path-sum-in-a-binary-tree/

  private static int maxSum(Node<Integer> btree, Result result) {

    if (btree == null)
        return 0;
    int l = maxSum(btree.left, result);
    int r = maxSum(btree.right, result);

    System.out.println(l + " " + r + " " + btree.data);
    int maxSingle = Math.max(Math.max(l, r) + btree.label, btree.label);
    int maxTop = Math.max(l + r + btree.label, maxSingle);

    result.val = Math.max(maxTop, result.val);
    return maxSingle;
}

private static Node<Integer> createBinaryTree(Integer[] parent, Node<Integer> root) {
    Map<Integer, Node<Integer>> map = new HashMap<>();

    for (int i = 0; i < parent.length; i++) {
        map.put(i, new Node<>(i));
    }

    for (int i = 0; i < parent.length; i++) {
        if (parent[i] == -1) {
            root = map.get(i);
        } else {
            Node<Integer> par = map.get(parent[i]);
            Node<Integer> child = map.get(i);
            if (par.left == null) {
                par.left = child;
            } else {
                par.right = child;
            }
        }
    }

    return root;
}

Answer 2

Я бы разделил ваш вопрос на 2 разных вопроса:

1. Построить дерево из ваших данных
2. Найти максимальную сумму

Я написал кодв PHP, но вы можете конвертировать его на любой язык (мой навык JAVA немного ржавый ...)

Построить дерево :

$parent = array( -1, 0, 0, 2, 3 );
$values = array(0, 4, 6, -11, 3 );

function getNode($id, $data) {
    return array("id" => $id, "data" => $data, "childs" => array());
}
function addToTree($node, &$root, $parentsId) {
    if ($parentsId == -1)
        $root = $node;
    else if ( $root["id"] == $parentsId)
        $root["childs"][] = $node;
    else
        foreach($root["childs"] as &$child)
            addToTree($node, $child, $parentsId);
}

$root = null;
for($i = 0; $i < count($parent); $i++) {
    addToTree(getNode($i, $values[$i]), $root, $parent[$i]);
}

Теперь root, если вы содержите «древовидные» данные.Обратите внимание, что этот код работает только в том случае, если узлы заданы в правильном порядке, и он не может поддерживать множественный корень (предположим, дерево, а не лес)

Найти максимальный путь :

function maxPath($node) {
    $sum = $node["data"];
    foreach($node["childs"] as $child) {
        $s = maxPath($child);
        if ($s > 0) // if its not positive then don't take it
            $sum += $s;
    }
    return $sum;
}

Эта рекурсивная функция получит ваш max-sum-path.Обратите внимание, что это позволит использовать несколько дочерних элементов для каждого узла, а также путь может иметь форму звезды.