从二叉搜索树中找到两个数使它们的和等于给定的数字K

Question

给定一个唯一整数的二叉搜索树和一个数字K，找出BST中的一对（a，b），使得a + b = k。 限制条件： 您不能更改树的结构，否则我们可以将其转换为已排序的双向链表，并在O（N）中找到一对。

方法应该是原地进行的。

需要O（N）解决方案。

我考虑过类似于在已排序数组中查找一对的方式，从左到右运行两个指针，另一个从右到左。但是，我无法清楚地实现它。

- Green goblin

---

我认为你的解决方案很好，你进行了两次中序遍历：从左到右，从右到左。如果（a + b）> k，则增加从左到右的迭代器。在另一种情况下，增加从右到左的迭代器。 - Samuel Gosselin

我知道这很好，但问题是我们如何在线性情况下实现它，特别是在树的情况下？ - Green goblin

a、b和k必须是正数吗？还是可以有任意一个为负数？ - orlp

它们也可以是负数。例如：-3 + 5 = 2 - Green goblin

显然的递归算法是O(N) - 从根节点开始，从左到右遍历从左子树开始，从右到左遍历从右子树开始。 - stark

如果您可以将树转换为双向链表，您如何在O(n)时间内找到a和b？ - Roman Dzhabarov

Answer 1

如Samuel所说，我也认为您的解决方案应该可行。 使用两个指针或迭代器，一个从左到右（从小到大），另一个从右到左（从大到小）。 如果(a + b) > k，则迭代右侧指针/迭代器（下一个较小值），否则迭代左侧指针/迭代器（下一个较大值）。 当a >= b时可以停止。 即使在不平衡的树中，运行时间也是线性的。 每个节点最多访问一次。

我认为在这种情况下，真正的函数递归会变得有些复杂。 因此最好使用两个自制堆栈来在一个函数中进行递归。 类似于以下内容：

a = b = root;
while (a.left) {
    astack.push(a)
    a = a.left
}
while (b.right) {
    bstack.push(b)
    b = b.right
}


while (a.value < b.value) {
    if (a.value + b.value == k) found!
    if (a.value + b.value < k) {
        if (a.right){
            a = a.right
            while (a.left) {
                astack.push(a)
                a = a.left
            }
        } else a = astack.pop()
    } else {
        if (b.left){
            b = b.left
            while (b.right) {
                bstack.push(b)
                b = b.right
            }
        } else b = bstack.pop()
    }
}

- Ole Dittmann

---

我认为你的算法可能会进入无限循环，例如在以下情况下：（20（10（5）（15））（））（在评论中不能做得比LISP符号更好），我认为你的算法在定位到15后不会正确地找到下一个数字。 - Ivan Vergiliev

@Ivan：我不明白你的意思。 - Ole Dittmann

你不能仅仅在堆栈中存储引用。在 stack.add(a) 执行之后，所有的堆栈元素最终都会成为相同的值。 - JavaDeveloper

当 (节点 != null) { // 新引用 :) TreeNode refNode = 节点; stackLow.push(refNode); 节点 = 节点.left; } - JavaDeveloper

Answer 2

我同意使用双指针的方法。我也考虑过这个方法。然而，如果我们尝试使用递归，代码将变得非常复杂/混乱。另一种方法是使用栈，就像排名最高的答案所提到的那样。但是，如果我们必须使用空间来使其变得更简单，我们完全可以避免使用双指针的方法。

我在这里使用了不同的方法。按任意顺序遍历树并将元素插入HashSet中。一旦该集合被填充，遍历集合元素，并只检查目标和与当前数字之间的差异是否存在。如果存在，则返回；否则移至下一个元素。

这仍然是O(n)的方法，但使用O(n)和更容易理解。

- Bhavya

---

简单而不失优雅的方法 - Anuj Mehta

这可能更简单的编码，仍然是O(n)，但常数因子更差。在插入期间对每个元素进行哈希，然后在遍历期间再次进行哈希，比只是相互遍历指针要更费力！此外，哈希表的大小可能约为2N。内存局部性很糟糕。如果哈希表不适合缓存，并且哈希函数发挥作用，则大多数哈希表访问将在缓存中未命中。访问的随机性将击败预取。 - Peter Cordes

Answer 3

我们同时遍历BST的正常中序遍历和反向中序遍历。在反向中序遍历中，我们从最右边的节点开始，即最大值节点。在正常中序遍历中，我们从最左边的节点开始，即最小值节点。我们将两个遍历中当前节点的总和相加，并将此总和与给定的目标总和进行比较。如果总和与目标总和相同，则返回true。如果总和大于目标总和，则移动到反向中序遍历中的下一个节点，否则移动到正常中序遍历中的下一个节点。如果任何一个遍历没有找到一对节点，则返回false。

   boolean isPairPresent(Node3 root, int sum) 
   {
    Stack<Node3> stack1 = new Stack<Node3>();
    Stack<Node3> stack2 = new Stack<Node3>();

    boolean done1 = false;
    boolean done2 = false;

    int val1 = 0, val2 = 0;
    Node3  curr1 = root, curr2 = root;

    while(true) {

        while(done1 == false)   {
            if(curr1 != null)   {
                stack1.push(curr1);
                curr1 = curr1.left;
            } else {
                if(stack1.isEmpty())
                    done1 = true;
                else    {
                    curr1 = stack1.pop();
                    val1 = curr1.data;
                    curr1 = curr1.right;
                    done1 = true;
                }
            }   
        }

        while(done2 == false)   {
            if(curr2 != null)   {
                stack2.push(curr2);
                curr2 = curr2.right;
            } else {
                if(stack2.isEmpty())
                    done2 = true;
                else {
                    curr2 = stack2.pop();
                    val2 = curr2.data;
                    curr2 = curr2.left;
                    done2 = true;
                }
            }
        }

        if((val1 != val2) && (val1+val2 == sum))    {
            System.out.println("Pair found: "+val1+" + "+val2+" = "+sum);
            return true;
        } else if(val1 + val2 > sum) {
            done2 = false;
        } else if(val1 + val2 < sum)
            done1 = false;

        if(val1 >= val2)
            return false;
    }
}

- vatsal sevak

Answer 4

首先对树进行中序遍历，并将结果存储在数组a[]中，然后

i = 0 ; j = n;
while(i<=j<=n)
{
  if(a[i]+a[j] == k)
  {
    printf("pair is == %d & %d \n", a[i],a[j]);
    i++;
  }
  else if(a[i]+a[j] > k)
    j--;
  else if(a[i]+a[j] < k)
    i++;
}

- Dheeraj Agrawal

Answer 5

另一个解决上述问题的方案（它需要O(n)的空间，但实现比在BST中查找下一个更大/更小的元素要简单得多） 对给定的二叉树执行中序遍历并将元素存储在数组中。生成的数组将是排序后的。从比较A[1]+A[n]和k开始。

Initialize i=1, j=n

while(A[i]+A[j] <> k)
if A[i]+A[j] < k
  i++;
else
  j--;// typo

- Harshal Waghmare