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