將節點的值替換爲其所有後代的總和

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

Answer 2

我還沒有真正測試這一點，但我覺得這樣的事情應該工作ŧ o幫助獲得節點孩子的總和。然後你可以通過這個總和來替換每個節點的值。

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

Answer 3

要存儲所有子節點在節點中的總和，請將您的節點/樹與特定作業非常接近。那麼在TNode級別中使用遍歷和求和方法會不會更好？它現在在哪裏？

另一個問題：如果您需要重新計算樹，則必須再次遍歷整個樹，或者您必須知道，您是否已經計算了總和，並且自那時起沒有對值或樹進行修改。但是，如果插入一個節點後立即計算總和，那麼樹會總是反映總和？每個TNode的數據是否最終？嗯 - 它不能，如果它首先是節點自己的值，然後是節點的值加上所有的後代。

Answer 4

不知道如果我得到這個問題正確地考慮到從塔馬斯最接受的答案的複雜性，但下面簡單的代碼似乎爲我工作（糾正我，如果我缺少一個測試用例）：

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 5

該代碼用於存儲在相應的節點，其中左和右子樹的原始數據被添加的目的（純遞歸的方式）

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 6

我認爲這可能是簡單的解決方案：

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;   

}