java - 将节点的值替换为其所有后代的总和

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;
}

如果您不想包含原始值，那么单次递归传递是不够的，因为当您计算具有两个叶子 L1 和 L2 的非叶节点 N 的值时，L1 和 L2 中的值已经更新为零，所以你不能使用 L1 和 L2 的原始值来存储 N。如果你被允许在节点中添加一个新的 originalItem 条目，你可以在那里存储原始值，使用我上面的解决方案，然后运行最后一次传递，为树中的每个节点从 item 中减去 originalItem 的值:

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);
}