在 Java 中将二叉树转换为求和树

Question

REFERENCE 我正在复制粘贴问题和在 C 中有效的解决方案，我无法在 Java 中使用它。我的理解主要是因为在 Java 中参数是按值传递的，这导致维护 "old_value" 状态的问题。但我什至尝试将其更改为带有 set 和 get 的自定义 MyInt，但仍然无法正常工作。所以，可能我在这里也遗漏了其他东西。请建议。

Given a Binary Tree where each node has positive and negative values. Convert this to a tree where each node contains the sum of the left and right sub trees in the original tree. The values of leaf nodes are changed to 0.

比如下面这棵树

              10
           /      \
         -2        6
       /   \      /  \ 
      8     -4    7    5

应该改为

             20(4-2+12+6)
           /      \
      4(8-4)      12(7+5)
       /   \      /  \ 
      0      0    0    0

代码：

int toSumTree(struct node *node)
{
    // Base case
    if(node == NULL)
      return 0;


// Store the old value
int old_val = node->data;

// Recursively call for left and right subtrees and store the sum as
// new value of this node
node->data = toSumTree(node->left) + toSumTree(node->right);

// Return the sum of values of nodes in left and right subtrees and
// old_value of this node
return node->data + old_val;

}

Java代码：

public static int sumTree(Node node){
        if(node == null)
            return 0;
        MyInt old_value = new MyInt(node.data);
        node.data = sumTree(node.left) + sumTree(node.right);
        return node.data + old_value.getData();
    }

Answer 1

我被运行测试错了。相同的代码逻辑将在 Java 中工作，并且在评论中正确指出按值传递没有区别，因为值正在返回。以下是工作 Java 代码：

public static int sumTree(TreeNode node){
        if(node == null)
            return 0;
        int old_value = node.value;
        node.value = sumTree(node.left) + sumTree(node.right);
        return node.value + old_value;
    }

在 Java 中将二叉树转换为求和树

convert binary tree to sum tree in Java

java

algorithm

binary-tree