在BST尋找元素總結爲提供的值

Question

我試圖得到一個辦法來解決這個問題

Find two elements in balanced BST which sums to a given a value. 

約束時間O（n）和空間O（LOGN）。

我想知道下面的算法是否有效。

int[] findSum(Node root, int sum){ 
    int[] sumArray; 
    for (int i=0;i<sum;i++) { 
     if (root.contains(i) && root.contains(sum-i)) { 
     sumArray[0] = i; 
     sumArray[1] = sum-i; 
     } 
    } 
} 

我明白我的方法可能是錯誤的。我將不勝感激任何反饋/更正我的僞代碼/更好的算法

Answer 1

我相信你的方法將工作，但沒有適當的時間限制。

我們首先分析一下這個算法的複雜性。請注意，這裏有兩個不同的參數需要考慮。首先，BST中有元素的總數。如果您使BST變大或變小，則算法完成需要更多或更少的時間。我們稱這個數字爲n。其次，有你想要的值總和的總數。我們稱之爲U.

所以我們來看看你現在使用的算法。現在，它迭代循環O（U）次，每次迭代檢查BST中是否存在兩個值。每個BST查找需要花費時間O（log n），因此算法的總工作量爲O（U log n）。但是，您的算法僅使用恆定空間（即空間O（1））。

不幸的是，這個運行時間並不好。如果目標數量非常大（例如，1,000,000,000），那麼你的算法將花費很長時間才能完成，因爲U將會非常大。

所以現在的問題是如何更有效地解決這個問題。幸運的是，我們可以使用一個非常可愛的算法來解決這個問題，它將利用BST的元素以排序順序存儲的事實。

讓我們從解決一個與你所構造的問題有點不同的類似問題開始。假設不是給你一個BST和一個目標數字，我給你一個排序的數組和一個目標數字，然後問同樣的問題：在這個有序數組中有兩個數字總結到目標？舉例來說，我可能會給你此陣：

0 1 3 6 8 9 10 14 19 

讓我們假設你想知道，如果這個數組中的兩個數字加起來爲16.你會怎樣做呢？

你可以嘗試以前的方法：檢查數組是否包含0和16,1和15,2和14等，直到找到一對或用完的值檢查。檢查排序數組中是否存在元素需要花費時間O（log n）使用二分搜索，因此該算法仍然需要O（U log n）時間。 （如果你知道這些值很好地分佈，這會使O（U log log n）運行時期望得到，但是這個大的U項仍然是一個問題），你可以想象使用interpolation search可以提高速度。

所以讓我們考慮一種不同的方法。從根本上說，你在做什麼需要你明確地列舉所有總和爲U的對。然而，它們中的大多數不會在那裏，並且實際上，大部分時間對中的兩個都不會是元件在那裏。我們可以通過使用以下算法使事情變得更快：

• 對於數組x的每個元素，檢查U-x是否在數組中。
• 如果是這樣，報告成功。
• 否則，如果沒有這種對存在時，報告故障。

該算法將要求您查看數組中的總共O（n）個元素，每次執行O（log n）工作以查找匹配對。在這種最壞的情況下，這將花費O（n log n）時間並使用O（1）空間。如果U是一個很大的數字，這比以前好得多，因爲根本不再依賴U！

不過，我們可以通過使有關問題的結構巧妙的觀察進一步加快速度。假設我們正在查看數組中的數字x並執行二進制搜索以查找U-x。如果我們找到了，我們就完成了。如果沒有，我們會發現數組中的第一個數字大於U - x。我們稱這個數字爲z。

所以現在假設我們想看看是否一個數y可能是總結了至U的對的一部分，而且，假設y是大於x。在這種情況下，我們知道，

Y + Z

> X + Z

> X +（U - X）

= U

該說什麼是y和z的總和是比U大，所以它不可能是U.這是什麼？ EAN？好吧，我們z實測，試圖做的是將配對X元素總結到U.我們剛剛表明的是，如果你嘗試到z的陣列中添加任何數量是更大的二進制搜索總數必須超過U.換句話說，z不能與大於x的任何東西配對。同樣，任何除z大不能大於x還有更大的配對，因爲它會要總結的東西比U.

基於這一觀察時，我們可以嘗試使用不同的算法。讓我們把我們的數組，不如以前了，看看我們是否能夠找到一對總計爲16：

0 1 3 6 8 9 10 14 19 

讓我們保持兩個指針 - 一個「左側」指針LHS和「右側」指針RHS：

0 1 3 6 8 9 10 14 19 
^      ^
lhs      rhs 

當我們總結一下這兩個數字，我們回到19，超過U.現在，任何一對，我們加起來已數量的具有其較低的數量至少爲大LHS號，它是0。因此，如果我們試圖總結任何對這裏使用的19號，我們知道，總和將太大。因此，我們可以從考慮消除含19任何對這使得

0 1 3 6 8 9 10 14 19 
^     ^
lhs     rhs 

現在，看看這個總和（14），這是太小了。使用和以前類似的邏輯，我們可以放心地說，使用0的剩餘數組中的任何和必須最終給出小於16的總和，因爲總和中的第二個數最多爲14。因此，我們可以排除0：

0 1 3 6 8 9 10 14 19 
    ^    ^
    lhs     rhs 

我們開始看到一個模式：

• 如果金額過小，推進LHS。
• 如果總和太大，則遞減rhs。

最終，我們要麼找到一對總計爲16，或LHS和rhs將碰到彼此，在這一點我們保證了不會對總和達到16

跟蹤通過這個算法，我們得到了

0 1 3 6 8 9 10 14 19 
    ^    ^
    lhs     rhs (sum is 15, too small) 

0 1 3 6 8 9 10 14 19 
    ^   ^
     lhs    rhs (sum is 17, too big) 

0 1 3 6 8 9 10 14 19 
    ^  ^
     lhs   rhs  (sum is 13, too small) 

0 1 3 6 8 9 10 14 19 
     ^  ^
     lhs  rhs  (sum is 16, we're done!) 

等瞧！我們得到了我們的答案。

那麼這個速度有多快呢？那麼，在每次迭代中，lhs下降或rhs上升，並且當它們相遇時算法停止。這意味着我們進行O（n）次迭代。每次迭代最多可以持續工作，因此每次迭代至多需要O（1）次工作。這給出了O（n）的總時間複雜度。

太空如何？那麼，我們需要存儲兩個指針，每個指針佔用O（1）空間，因此總空間使用量爲O（1）。大！

但這與你的問題有什麼關係？連接是這樣的：在每個時間點，這個算法只需要記住數組中的兩個數字。然後它需要能夠從一個元素前進到下一個元素或從一個元素前進到前一個元素。這就是它必須做的。

因此，假設不是使用排序的數組，而是使用二叉搜索樹。從兩個指針開始，一個指向最小的節點，另一個指向最大的指針。一旦你有了這個設置，你就可以模擬上面的算法，用「移動到lhs的中間繼任者」和「移動到rhs的預定任務」替換「遞增lhs」和「遞減rhs」。可以實現這些操作，以便它們總共使用O（log n）空間（假定樹是平衡的）並且使得每種類型的n個操作的任何序列總共需要O（n）個時間總計（不管是否樹是平衡的）。因此，如果您要使用修改後的算法在BST上工作，您將得到一個花費時間O（n）並僅使用O（log n）空間的算法！

實現細節有點棘手，我將把這部分作爲練習留給你。如果你不熟悉後繼者和前輩的話，網上有很多很好的資源。它們是BST的標準算法，對於瞭解它們非常有用。我也將數組算法的正確性證明作爲練習，儘管它並不難。

希望這會有所幫助！

Answer 2

我想你必須搜索樹兩次。但首先，你需要一個名爲sum的整數，但它突然間是一個數組？這是一個錯字嗎？我假設你打算接受一個和數組。

您必須遍歷樹，並且對於每個節點，從根調用另一個遍歷，查找可以添加到等於總和的第一個節點元素的節點。

另外你不能有總和是一個變量和數組在同一個方法。

現在我剛剛看到您的編輯，以數字17爲例。您首先搜索0，如果您找到它，則調用另一個搜索，從根開始搜索17 -0。如果你沒有找到它，增加0至1和搜索17-1，直到你找到兩個數字給你17

編輯

//we're looking for two numbers that equal 17 when added 
Node runner; 
Node root; 
int i; 
int [] sum_total; 

void findSum(int sum){ 
    int search_1st = 0; 
    sum_total = new int[2]; 
    search(int search_1st); 
} 

search(Node root, int num1){ 
    if(i == 3){ 
     return; 
    } 
    Node runner = root; 
    if(ruunner == null){ 
    return ; 
    } 
    if(runner.element == num1){ 
     sum_total[i] = num1; 
     i++; 
     if(i == 3){ 
      return; 
     } 
     //now search for sum - num1 with root 
     search(root, sum - num1); 
    }else{ 
     if(runner.left < num1){ 
      search(runner.right, num1); 
     }else{ 
      search(runner.left, num1); 
     } 
    } 
} 

Answer 3

從http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/

/* In a balanced binary search tree isPairPresent two element which sums to 
    a given value time O(n) space O(logn) */ 
#include <stdio.h> 
#include <stdlib.h> 
#define MAX_SIZE 100 

// A BST node 
struct node 
{ 
    int val; 
    struct node *left, *right; 
}; 

// Stack type 
struct Stack 
{ 
    int size; 
    int top; 
    struct node* *array; 
}; 

// A utility function to create a stack of given size 
struct Stack* createStack(int size) 
{ 
    struct Stack* stack = 
     (struct Stack*) malloc(sizeof(struct Stack)); 
    stack->size = size; 
    stack->top = -1; 
    stack->array = 
     (struct node**) malloc(stack->size * sizeof(struct node*)); 
    return stack; 
} 

// BASIC OPERATIONS OF STACK 
int isFull(struct Stack* stack) 
{ return stack->top - 1 == stack->size; } 

int isEmpty(struct Stack* stack) 
{ return stack->top == -1; } 

void push(struct Stack* stack, struct node* node) 
{ 
    if (isFull(stack)) 
     return; 
    stack->array[++stack->top] = node; 
} 

struct node* pop(struct Stack* stack) 
{ 
    if (isEmpty(stack)) 
     return NULL; 
    return stack->array[stack->top--]; 
} 

// Returns true if a pair with target sum exists in BST, otherwise false 
bool isPairPresent(struct node *root, int target) 
{ 
    // Create two stacks. s1 is used for normal inorder traversal 
    // and s2 is used for reverse inorder traversal 
    struct Stack* s1 = createStack(MAX_SIZE); 
    struct Stack* s2 = createStack(MAX_SIZE); 

    // Note the sizes of stacks is MAX_SIZE, we can find the tree size and 
    // fix stack size as O(Logn) for balanced trees like AVL and Red Black 
    // tree. We have used MAX_SIZE to keep the code simple 

    // done1, val1 and curr1 are used for normal inorder traversal using s1 
    // done2, val2 and curr2 are used for reverse inorder traversal using s2 
    bool done1 = false, done2 = false; 
    int val1 = 0, val2 = 0; 
    struct node *curr1 = root, *curr2 = root; 

    // The loop will break when we either find a pair or one of the two 
    // traversals is complete 
    while (1) 
    { 
     // Find next node in normal Inorder traversal. See following post 
     // http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/ 
     while (done1 == false) 
     { 
      if (curr1 != NULL) 
      { 
       push(s1, curr1); 
       curr1 = curr1->left; 
      } 
      else 
      { 
       if (isEmpty(s1)) 
        done1 = 1; 
       else 
       { 
        curr1 = pop(s1); 
        val1 = curr1->val; 
        curr1 = curr1->right; 
        done1 = 1; 
       } 
      } 
     } 

     // Find next node in REVERSE Inorder traversal. The only 
     // difference between above and below loop is, in below loop 
     // right subtree is traversed before left subtree 
     while (done2 == false) 
     { 
      if (curr2 != NULL) 
      { 
       push(s2, curr2); 
       curr2 = curr2->right; 
      } 
      else 
      { 
       if (isEmpty(s2)) 
        done2 = 1; 
       else 
       { 
        curr2 = pop(s2); 
        val2 = curr2->val; 
        curr2 = curr2->left; 
        done2 = 1; 
       } 
      } 
     } 

     // If we find a pair, then print the pair and return. The first 
     // condition makes sure that two same values are not added 
     if ((val1 != val2) && (val1 + val2) == target) 
     { 
      printf("\n Pair Found: %d + %d = %d\n", val1, val2, target); 
      return true; 
     } 

     // If sum of current values is smaller, then move to next node in 
     // normal inorder traversal 
     else if ((val1 + val2) < target) 
      done1 = false; 

     // If sum of current values is greater, then move to next node in 
     // reverse inorder traversal 
     else if ((val1 + val2) > target) 
      done2 = false; 

     // If any of the inorder traversals is over, then there is no pair 
     // so return false 
     if (val1 >= val2) 
      return false; 
    } 
} 

// A utility function to create BST node 
struct node * NewNode(int val) 
{ 
    struct node *tmp = (struct node *)malloc(sizeof(struct node)); 
    tmp->val = val; 
    tmp->right = tmp->left =NULL; 
    return tmp; 
} 

// Driver program to test above functions 
int main() 
{ 
    /* 
        15 
       / \ 
       10  20 
      /\ /\ 
      8 12 16 25 */ 
    struct node *root = NewNode(15); 
    root->left = NewNode(10); 
    root->right = NewNode(20); 
    root->left->left = NewNode(8); 
    root->left->right = NewNode(12); 
    root->right->left = NewNode(16); 
    root->right->right = NewNode(25); 

    int target = 28; 
    if (isPairPresent(root, target) == false) 
     printf("\n No such values are found\n"); 

    getchar(); 
    return 0; 
} 

Answer 4

或者，遍歷樹並將所有值存儲在HashSet中。然後再做一次遍歷，看看是否（target - nodeValue）在集合中。它可以在O（n）時間，O（n）空間完成。

Answer 5

這個想法與之前的解決方案相同，只是我在做兩個堆棧 - 一個跟隨inorder（stack1），另一個跟隨反向 - inorder order（stack2）。一旦我們到達BST中最左側和最右側的節點，我們就可以開始比較它們。

如果總和小於所需值，則從堆棧1彈出，否則從堆棧2彈出。以下是相同的java實現：

public int sum2(TreeNode A, int B) { 
    Stack<TreeNode> stack1 = new Stack<>(); 
    Stack<TreeNode> stack2 = new Stack<>(); 
    TreeNode cur1 = A; 
    TreeNode cur2 = A; 

    while (!stack1.isEmpty() || !stack2.isEmpty() || 
      cur1 != null || cur2 != null) { 
     if (cur1 != null || cur2 != null) { 
      if (cur1 != null) { 
       stack1.push(cur1); 
       cur1 = cur1.left; 
      } 

      if (cur2 != null) { 
       stack2.push(cur2); 
       cur2 = cur2.right; 
      } 
     } else { 
      int val1 = stack1.peek().val; 
      int val2 = stack2.peek().val; 

      // need to break out of here 
      if (stack1.peek() == stack2.peek()) break; 

      if (val1 + val2 == B) return 1; 

      if (val1 + val2 < B) { 
       cur1 = stack1.pop(); 
       cur1 = cur1.right; 
      } else { 
       cur2 = stack2.pop(); 
       cur2 = cur2.left; 
      } 
     } 
    } 

    return 0; 
}