给你一个 BST 数字。您必须在 O(n) 时间和 O(1) 空间内找到其中的两个数 (a, b) 使得 a + b = S
。
可能是什么算法?
一种可能的方法是将 BST 转换为双向链表,然后从前端和后端开始:
if front + end > S then end--
或者:
if front + end < S then front++
最佳答案
我最近在一次采访中被问到这个问题。当我被卡住时,我得到了提示。
提示:假设您需要为排序数组解决同样的问题,那么您将如何解决它。
我:保留两个指针。一个在开头,另一个在结尾。如果这些指针处的元素总和小于所需总和,则将前指针向右移动,否则将后指针向左移动。
面试官:你怎么能对二叉搜索树做同样的事情呢?
我:做一个中序遍历,并将指向节点的指针保存在一个数组中。并使用与数组相同的逻辑。
面试官:是的,行得通。但是空间复杂度是O(n)。你能减少它吗?
我(经过很多时间):好的,使用 this 将 BST 转换为双向链表。算法。然后使用与数组相同的逻辑。由于递归,空间复杂度为 O(lg(n))。
关于algorithm - 在二叉搜索树中找到两个数相加等于第三个数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1753843/