用節點總和大於或等於節點替換BST節點

Question

我想知道以下問題的算法：
「給定一個BST（可能有重複的節點），將每個節點的值替換爲是所有節點的值大於等於當前節點的值的總和。「

實施例：

       5    15 
          2 10  o/p: 17 10 

我的反向中序遍歷保持變量 '總和' 做到了。以下是代碼：
------------------------------------------- -------------------------------------------------- ----------

//總和是一個單一的元件陣列。初始和[0] = 0
public static void replaceNodeValue（BSTNode root，int [] sum）{
if（root == null）return;
replaceNodeValue（root.right，sum）;
root.data =（sum [0] = sum [0] + root.data）;
replaceNodeValue（root.left，sum）;
}

問題是這樣的代碼只能如果樹不包含重複的節點。我正在尋找將處理重複節點的正確算法。

在一種情況下的代碼將失敗是：

       5 
          5  5 

請幫助。 謝謝

Answer 1

這是一個O（n）問題的解決方案。通過遍歷樹的每個node.Since樹訪問數比更大的每個節點的值需要被訪問的所有節點的複雜性將是O（n）的

int sum_all(Node root) 
{ 
    if(root == null) return 0; 
    return root.data + sum_all(root.left) + sum_all(root.right); 
} 

void replace_keys(Node root, int total) 
{ 
    if(root == null) return; 

    int leftsum = sum_all(root.left); 
    root.data = (total - leftsum - root.data); 

    replace_keys(root.left, total); 
    replace_keys(root.right, total); 
} 

void replace_keys(Node root) 
{ 
    int total = sum_all(root); 
    replace_keys(root, total); 
} 

Answer 2

首先，遍歷BST並將每個節點推入一個數組。其次，對數組進行排序。

最後，再遍歷BST，並在數組的幫助下進行替換。

Answer 3

這個問題可以解決遞歸，其背後是想法：

對於在BST任何節點：

• 右子樹有大於或等於 父的所有元素。
• 左子樹的值小於父元素。

有了這想法，

• 對於每一個節點上，我們與和替換它的價值它是正確的 子樹+它自己的價值。 （我們計算右子樹和遞歸:)）

• 然後我們去到它留給孩子，取代它的價值與它的 父母的價值+它自己的價值+它的右子樹的最大總和。

遞歸的終止條件發生在遇到沒有右子樹的節點時。發生這種情況時，節點的值將是它自己的值，我們將返回。

的C/C++ ISH僞代碼：

NODE* recSum(root){ 
    getSum(root); 
    return root; 
} 

int getSum(NODE *n){ 
    if (n->r == NULL) return n->val; 

    else{ 
     n->val = getSUM(n->r) + n->val; 
     n->l->val = getSUM(n) + getSUM((n->l)->r); 
    } 
} 

Answer 4

ALGO：

爲了遍歷做反向，並更新總和

這裏是java實現

public static void modifyWithSumOfGreaterNodes(BinaryTreeNode<Integer> bst) { 
    doModifyWithSumOfGreaterNodes(bst, new MutableInteger(0));  
} 

private static void doModifyWithSumOfGreaterNodes(BinaryTreeNode<Integer> bst, MutableInteger sum) { 
    if (bst == null) { 
     return ; 
    } 

    doModifyWithSumOfGreaterNodes(bst.getRight(), sum); 
    sum.add(bst.getData()); 
    bst.setData(sum.getValue()); 
    doModifyWithSumOfGreaterNodes(bst.getLeft(), sum);  
} 

這裏是單元測試

@Test 
public void replaceBSTNodesWithSumOfNodesGreaterOrEqualToNodeTest() { 

    BinaryTreeNode<Integer> eighty = new BinaryTreeNode<Integer>(80); 
    BinaryTreeNode<Integer> sixty = new BinaryTreeNode<Integer>(60); 
    BinaryTreeNode<Integer> forty = new BinaryTreeNode<Integer>(40); 
    BinaryTreeNode<Integer> twenty = new BinaryTreeNode<Integer>(20); 
    BinaryTreeNode<Integer> seventy = new BinaryTreeNode<Integer>(70, sixty, eighty); 
    BinaryTreeNode<Integer> thrity = new BinaryTreeNode<Integer>(30, twenty, forty); 
    BinaryTreeNode<Integer> root = new BinaryTreeNode<Integer>(50, thrity, seventy); 

    BinaryTreeUtil.modifyWithSumOfGreaterNodes(root); 

    assertThat(BinaryTreeUtil.iPostOrder(root).toArray(new Integer[0]), equalTo(new Integer[]{350,300,330,210,80,150,260})); 


} 

Answer 5

這裏是在Java程序的完整

BinarySearchTree類定義

public class BST<T> { 

public Node root; 

static class Node<T>{ 
public Node left; 
public Node right; 
public T data; 

Node(T data){ 
    this.data =data; 
} 
} 

} 

實際的類定義是做其中每個節點替換都大節點的總和真正的東西給出BST

public class TestGreaterNodeBST { 



    public static void main(String[] args) { 
     BST<Integer> bst = new BST<Integer>(); 
     bst.root= new BST.Node<Integer>(50); 
     bst.root.left =new BST.Node<Integer>(30); 
     bst.root.right =new BST.Node<Integer>(80); 
     bst.root.right.left =new BST.Node<Integer>(70); 
     bst.root.right.left.left =new BST.Node<Integer>(60); 
     bst.root.right.right =new BST.Node<Integer>(100); 
     bst.root.right.right.right =new BST.Node<Integer>(120); 
     bst.root.right.right.right.left =new BST.Node<Integer>(110); 
     bst.root.right.right.right.right =new BST.Node<Integer>(150); 

     printInOrderDescending(bst.root); 
     System.out.println(); 
     System.out.println(); 
     transformToGreaterNode(bst.root, 0); 
     printInOrderDescending(bst.root); 

    } 


    static void printInOrderDescending(BST.Node node){ 

     if(node==null){ 
      return; 
     } 

     printInOrderDescending(node.right); 
     System.out.println(node.data); 
     printInOrderDescending(node.left); 

    } 



    static Integer transformToGreaterNode(BST.Node<Integer> node, Integer sum){ 

     if(node==null){ 
      return sum; 
     } 


     sum = transformToGreaterNode(node.right, sum); 

     Integer data = node.data; 
     node.data=sum; 
     sum = sum + data; 

     sum = transformToGreaterNode(node.left, sum); 

     return sum; 
    } 

}