查找两个数字在加起来第三号二叉搜索树 [英] Find two numbers in a binary search tree that add up to a third number

问题描述

您给出数字的BST。你必须找到两个数（A，B），它使得 A + B = S ，在O（n）时间及O（1）空间。

可能是什么算法？

一种可能的方式可以是两个为BST转换为双重链接列表，然后从前面和端开始：

 如果前+端＆GT;记者随后end--
 

或者

 如果前+端＆LT;记者随后前++
 

解决方案

正如其他人所提到的，你解决不了这个不断O（1）空间。此外，目前建议所有其他解决方案使用至少为O（log ^ 2 n）的空间，而不是O（log n）的空间：堆栈为O（log n）的帧，每一帧都有一个O（log n）的大小的指针。

现在，通过@ dharm0us目前公认的溶液通过将其转换成一个数组破坏BST。这是不必要的。相反，使用两个迭代器，一是做一个中序遍历和一个做反序遍历，并查找两个号码相同的，你会在数组中。每个迭代器有一个堆栈为O（log n）的每一帧持有O（log n）的大小指针总空间为O（log ^ 2 n）的帧。时间显然是线性O（N）。

You are given a BST of numbers. You have to find two numbers (a, b) in it such that a + b = S, in O(n) time and O(1) space.

What could be the algorithm?

One possible way could be two convert the BST to a doubly linked List and then start from the front and end:

if front + end > S then end--

Or:

if front + end < S then front++

解决方案

As others mentioned, you can't solve this in constant O(1) space. Furthermore, all the other solutions currently suggested use at least O(log^2 n) space, not O(log n) space: the stack has O(log n) frames and each frame has a O(log n) sized pointer.

Now, the currently accepted solution by @dharm0us destroys the BST by converting it into an array. This is unnecessary. Instead, use two iterators, one doing an in-order traversal and one doing a reverse-order traversal, and look for two numbers the same as you would in an array. Each iterator has a stack with O(log n) frames with each frame holding a O(log n) size pointer for total space O(log^2 n). The time is clearly linear O(n).

这篇关于查找两个数字在加起来第三号二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！