Замените значение узла на сумму всех его потомков

Question

private void sumNode(TNode node) {
    int sum = 0;
    if (node == null)
        return;

    sumNode(node.getLeft());
    sumNode(node.getRight());
    if (node.getLeft() != null && node.getRight() != null) {
        sum = (node.getData() + node.getLeft().getData() + node.getRight()
                .getData());
    } else if (node.getLeft() != null) {
        sum = (node.getData() + (Integer) node.getLeft().getData());
    } else if (node.getRight() != null) {
        sum = (node.getData() + node.getRight().getData());
    } else {
        sum = 0;
    }
    node.setData(sum);
}

Я знаю, что мой метод совершенно неправильный - я понятия не имею, как это сделать.

Я хочу заменить значение каждого узла на сумму всех его потомков, может кто-нибудь подсказать, как это сделать?делать?

У меня закончились идеи, как решить эту проблему.Будет оценен даже псевдокод.

Проблема:

• У моего дерева: 5 2 1 3 6 8
• Результат: 0 0 2 0 6 13,
• Ожидаемый результат: 0 0 4 0 8 20

Answer 1

Если вы хотите включить исходное значение узла в сумму, то это очень легко с рекурсией:

public void sumNode(TNode<E> root) {
    // For empty trees, do nothing.
    if (root == null)
        return;

    // Update the left subtree recursively.
    sumNode(root.left);

    // Update the right subtree recursively.
    sumNode(root.right);

    // At this point, all the elements in the left and right
    // subtrees are already summed up. Now we update the
    // sum in the root element itself.
    if (root.left != null)
        root.item += root.left.item;
    if (root.right != null)
        root.item += root.right.item;
}

Если вы не хотите включать исходное значение, то один рекурсивныйпрохода недостаточно, потому что к тому времени, когда вы вычисляете значение нелистового узла N с двумя листами L1 и L2, значения в L1 и L2 уже были обновлены до нулей, поэтому вы не можете использовать исходные значения L1 и L2для сохранения N. Если вам разрешено добавить новую запись originalItem в узел, вы можете сохранить исходное значение там, использовать мое решение выше и затем выполнить последний проход, который вычитает значение originalItem из itemдля каждого узла в дереве:

private void preprocessTree(TNode<E> root) {
    if (root == null)
        return;

    preprocessTree(root.left);
    preprocessTree(root.right);
    root.originalItem = root.item;
}

private void processTree(TNode<E> root) {
    if (root == null)
        return;

    processTree(root.left);
    processTree(root.right);
    if (root.left != null)
        root.item += root.left.item;
    if (root.right != null)
        root.item += root.right.item;
}

private void postprocessTree(TNode<E> root) {
    if (root == null)
        return;

    postprocessTree(root.left);
    postprocessTree(root.right);
    root.item -= root.originalItem;
}

public void sumTree(TNode<E> root) {
    preprocessTree(root);
    processTree(root);
    postprocessTree(root);
}

Answer 2

Не уверен, правильно ли я понимаю проблему, учитывая сложность наиболее приемлемого ответа от Тамаса, но мне кажется, что мне подходит следующий более простой код (поправьте меня, если я пропускаю тестовый пример):

1) Если вам нужно «исключить» текущее значение узлов из суммы, используйте следующее:

public static int sumDesc(TreeNode root)
{
    if(root == null) return 0;

    int temp = root.data;

    root.data = sumDesc(root.leftChild)+ sumDesc(root.rightChild);

    return root.data+temp;
}

2) Если вам необходимо «включить» текущее значение узлов, используйте следующее:

public static int sumDescInc(TreeNode root)
{
    if(root == null) return 0;

    root.data += sumDescInc(root.leftChild)+ sumDescInc(root.rightChild);

    return root.data;
}

Answer 3

Я думаю, что это может быть простое решение:

package tree;
import java.util.ArrayList;

public class TreeNode<T> {
    T data;
    ArrayList<TreeNode<T>> children;
    //generics don't make array
    public TreeNode(){
        children = new ArrayList<TreeNode<T>>(); 
    }
}

public static int sum(TreeNode<Integer> root)
{
        int s1=root.data;
        for(int i=0;i<root.children.size();i++)
            s1+=sum(root.children.get(i));

        return s1;          

}

Answer 4

этот код служит для цели, где добавляются исходные данные левого и правого поддерева, которые хранятся в соответствующем узле (чисто рекурсивный способ)

int sumofnodes(Node **root)
{
    if(*root==NULL)
        return 0;
    if((*root)->left==NULL && (*root)->right==NULL)
    {
        int temp=(*root)->val;
        (*root)->val=0;
        return temp;
    }
    int sum=sumofnodes(&(*root)->left)+sumofnodes(&(*root)->right);
    int data=(*root)->val;
    (*root)->val=sum;
    return (data+sum);


}

Answer 5

Для хранения суммы всех потомков в узле ваш узел / дерево очень близко связывается с конкретной работой.Не лучше ли иметь метод обхода и суммирования в классе TNode?Где это сейчас?

Еще один вопрос: если вам нужно пересчитать дерево, вам придется снова пройтись по всему дереву, или вы должны знать, вычислили ли вы уже сумму, и не нужно изменять значения илидерево произошло с тех пор.Но разве не будет легче вычислить сумму, как только вы вставите узел, чтобы дерево всегда отражало суммы?Являются ли данные каждого TNode окончательными?Хм - не может, если сначала это собственное значение узла, а затем значение узла плюс все потомки.

Answer 6

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

public int sum(Node node){
  return (!node.isLeaf()) ? sum(node.getLeftChild())+sum(node.getRightChild()) : node.getValue();
}