从BST找到两个数字,总和给定数字K.

Question

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

约束:

您无法更改树的结构,否则我们可以将其转换为已排序的双向链表,并在O(N)中填充该对.

该方法应该是就地的.

需要O(N)溶液.

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

Answer 1

正如塞缪尔已经说过,我也认为你的解决方案应该有效.两个指针或迭代器,一个从左到右(从小到大),一个从右到左(从大到小).如果(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()
    }
}