максимальная сумма данных всех детей и самого узла в дереве

Question

Это код, который я написал, но он продолжал давать неправильные ответы в этом тестовом примере: (Формат ввода: элементы в форме порядка уровней, разделенные пробелом (как сделано в классе). Порядок - Root_data, n (No_Of_Child_Of_ *) 1009 *), n дочерних элементов и т. Д. Для каждого элемента)

1 3 20 30 40 1 90 2 50 6 1 100 1 150 17 1000 2000 3000 4000 5000 6000 7000 85 86 87 88 89 92 93 94 95 96 1 80 1 83 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

ie  1:20,30,40
20:90   
30:50,6
40 100
90:150
50:17terms
6:80
100:83

class sol{
    int add;
    TreeNode<Integer> node;
    sol(int a, TreeNode<Integer> b){ add=a; node=b;}
}
public class Solution {

/*  TreeNode structure 
 * 
 * class TreeNode<T> {
        T data;
        ArrayList<TreeNode<T>> children;

        TreeNode(T data){
            this.data = data;
            children = new ArrayList<TreeNode<T>>();
        }
    }*/


    public static TreeNode<Integer> maxSumNode(TreeNode<Integer> root){
        // Write your code here
        sol ans= sum(root);
        return ans.node;
    }

    public static sol sum(TreeNode<Integer> root){
        if(root==null) return new sol(Integer.MIN_VALUE, null);

        int add=root.data;
        for(int i=0; i<root.children.size(); i++) add+=root.children.get(i).data;
        sol ans= new sol(add, root);

        for(int i=0; i<root.children.size(); i++){
            sol temp=sum(root.children.get(i));
            if(temp.add>add) ans=temp;
        }
        return ans;
    }       
}

Затем я немного изменил свою функцию, и это дало правильный ответ ie Я изменил последнее условие теста на это .

if(temp.add>ans.add) ans=temp;

Почему это происходит?

Answer 1

Это потому, что ans (и, следовательно, ans.add) меняется на протяжении итераций, чтобы соответствовать наибольшему найденному sum.

if (temp.add > ans.add) { ans = temp; }

add однако сохраняет только сумму root, которая была вычислена только один раз при первом вызове функции и не обновляется позже во втором l oop.

Подводя итог, вы хотите сравнить последовательные значения temp.add с самой большой суммой, найденной на тот момент (а это ans.add), а не со значением суммы в root, которая хранится в add.