我正在尝试找到解决问题的方法
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;
}
}
}
我知道我的方法可能是错误的。我将不胜感激对我的伪代码/更好的算法的任何反馈/更正
我相信您采用的方法会奏效，但没有适当的时间限制。
让我们从分析这个算法的复杂性开始。请注意，这里需要考虑两个不同的参数。首先，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 项仍然是一个问题）。
所以让我们考虑一种不同的方法。从根本上说，您正在做的事情需要您明确枚举总和为 U 的所有对。但是，它们中的大多数不会存在，事实上，大多数情况下，对中的任何元素都不存在. 通过使用以下算法，我们可以使事情变得更快：
该算法将要求您查看数组中总共 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。这是什么意思？好吧，我们通过尝试对与 x 配对的元素进行二分搜索来找到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
我们开始看到一种模式：
最终，我们要么找到总和为 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，
实现细节有点棘手，我将把这部分作为练习留给你。如果您不熟悉按顺序排列后继和前任，网上有很多很好的资源。它们是 BST 上的标准算法，非常有用。我还将把数组算法正确性的正式证明留作练习，尽管它并不太难。
希望这可以帮助！
我想你必须搜索树两次。但首先，您接收一个名为的整数sum，然后它突然变成了一个数组？那是错字吗？我假设你打算接受一个 sum 数组。
您必须遍历树，并且对于每个节点，从根调用另一个遍历，寻找可以添加到等于总和的第一个节点元素的节点。
此外，您不能在同一方法中将 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);
}
}
}
来自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;
}
或者，遍历树并将所有值存储在 HashSet 中。然后再进行一次遍历，看看(target - nodeValue) 是否在集合中。它可以在 O(n) 时间，O(n) 空间内完成。
这个想法与早期解决方案的想法相同，只是我用两个堆栈来做 - 一个在 inorder(stack1) 之后，另一个在反向之后 - inorder order(stack2)。一旦我们到达 BST 中最左边和最右边的节点，我们就可以开始将它们一起比较。
如果总和小于所需值，则从 stack1 中弹出，否则从 stack2 中弹出。以下是相同的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;
}