algorithm - 在二叉搜索树中找到两个数相加等于第三个数

Question

给你一个 BST 数字。您必须在 O(n) 时间和 O(1) 空间内找到其中的两个数 (a, b) 使得 a + b = S。

可能是什么算法？

一种可能的方法是将 BST 转换为双向链表，然后从前端和后端开始:

if front + end > S then end--

或者:

if front + end < S then front++

Answer 1

我最近在一次采访中被问到这个问题。当我被卡住时，我得到了提示。

提示:假设您需要为排序数组解决同样的问题，那么您将如何解决它。

我:保留两个指针。一个在开头，另一个在结尾。如果这些指针处的元素总和小于所需总和，则将前指针向右移动，否则将后指针向左移动。

面试官:你怎么能对二叉搜索树做同样的事情呢？

我:做一个中序遍历，并将指向节点的指针保存在一个数组中。并使用与数组相同的逻辑。

面试官:是的，行得通。但是空间复杂度是O(n)。你能减少它吗？

我(经过很多时间):好的，使用 this 将 BST 转换为双向链表。算法。然后使用与数组相同的逻辑。由于递归，空间复杂度为 O(lg(n))。