5

给定一个具有唯一整数和一个数字 K 的 BST。在 BST 中找到一对 (a, b)，使得 a + b = k。

约束：

您不能更改树的结构，否则我们可以将其转换为已排序的双向链表并在 O(N) 中找到该对。

该方法应该是就地的。

需要 O(N) 解决方案。

我想到了一些与运行两个指针有关的事情，一个从左到右，另一个从右到左，就像我们在排序数组中找到对的情况一样。但是，我无法清楚地了解如何实施它？

4

5 回答 5

9

正如塞缪尔已经说过的那样，我也认为您的解决方案应该有效。两个指针或迭代器，一个从左到右（从小到大），一个从右到左（从大到小）。如果 (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()
    }
}
于 2012-09-05T21:58:17.347 回答
2

我同意 2 指针方法可行。我确实想到了同样的事情。但是，我认为如果我们尝试使用递归，代码会变得非常复杂/混乱。另一种方法是使用堆栈作为评价最高的答案提及。但是，如果我们必须使用空间来降低复杂性，我们可以完全避免 2 指针方法。

我在这里使用了不同的方法。以您想要的任何顺序遍历树并将元素插入 HashSet。填充此集合后，遍历集合的元素并检查 target_sum 和当前数字之间是否存在差异。如果它确实返回或移动到下一个元素。

这仍然是 O(n) 方法的顺序，但使用 O(n) 并且在我看来更容易理解。

于 2014-10-28T02:33:48.647 回答
1

我们同时以 Normal Inorder 和 Reverse Inorder 遍历 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;
    }
}
于 2016-04-15T08:17:47.513 回答
0

上述问题的另一个解决方案（它占用 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
于 2013-01-26T16:57:29.253 回答
0

首先对树进行中序遍历并将结果存储在 中Array 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++;
}
于 2013-07-04T05:08:51.193 回答