在二叉搜索树中找到两个数使它们的和等于第三个数

Question

你被给定了一棵数字二叉搜索树。你需要在其中找到两个数(a,b)，使得它们的和等于S，时间复杂度为O(n)，空间复杂度为O(1)。

可能的算法是将BST转换为双向链表，然后从前面和末尾开始查找。

if front + end > S then end--

或者：

if front + end < S then front++

- Geek

---

这是作业吗？（通常最好提一下。） - ShreevatsaR

@ Peter：假设是正数，并且假设存在一个解。也可能存在多个解。 - Geek

将链表转换为双向链表（或任何其他数据结构）的空间复杂度并不是O(1)。 - paxdiablo

如果其中一个要求是O(1)空间，则这不是一个解决方案。实际上，即使是递归解决方案，其空间复杂度也不会比O(log n)更好。这些是固定要求还是愿望清单？ - paxdiablo

递归意味着堆栈空间为O(log n)。 - paxdiablo

Answer 1

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

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

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

面试官：您如何为二叉搜索树执行相同的操作？

我：进行中序遍历，并将节点指针保存在数组中。然后使用与数组情况下相同的逻辑。

面试官：是的，这可行。但空间复杂度为O(n)。您能减少吗？

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

- simplfuzz

---

为什么要把二叉搜索树转换成数组？为什么不能使用两个迭代器，一个进行中序遍历，另一个进行逆序遍历，并像在数组中一样查找两个数字？每个迭代器都具有一个指向当前节点的指针。 - Tyson Williams

“逆序遍历？你是指先序遍历吗？” - Raulp

Answer 2

尽管我尽力了，但我不确定在没有父指针的二叉树中是否可能实现。O(1)空间意味着既不能使用递归（堆栈增长为O(log n)），也不能复制到双向链表（O(n)）。你提到的方法确实是一个O(n)时间复杂度的解决方案，但它不适用于普通的二叉树。实际上，我在这里详细回答了一个类似的问题。那个问题之所以可以用O(n)空间解决，是因为它们最初没有排序。如果树包含父指针，则可以实现。如果子节点有指向其父节点的指针，则可以将树视为迭代处理的双向链表。

为了实现这个目标，您将运行起始指针到最左侧的节点，并将结束指针下移到最右侧的节点。您还需要维护两个变量来存储每个指针的最后移动（向上或横向，最初是向上），以便您可以智能地选择下一个移动（在您的问题中的front++和end--）。然后，您可以使用当前指针和最后移动，以及当前总和，来决定要移动哪个指针（以及如何移动）。

- paxdiablo

---

当我说将其转换为双向链表时，我并不是指将树复制到双向链表中。实际上，我是指通过使左右指针扮演NEXT和PREVIOUS的角色来将其转换为双向链表。 - Geek

你不能只使用next/previous将其转换为双向链表，除非你使用递归。而由于O(1)空间要求，所以不能使用递归。 - paxdiablo

由于我认为在不允许使用父指针的情况下，这个问题没有解决方案，因此我将其标记为CW。如果我的看法被证明是错误的，我会很高兴。 - paxdiablo

制作CW = ? 如果我找到解决方案，将会发布 :( - Geek

@Geek：社区维基。由于我实际上没有为您的问题提供答案，因此我将答案标记为CW（无论如何都不会获得声望）。这是因为，虽然我相信不存在解决方案，但我不确定，几乎肯定有比我更了解的人存在。 - paxdiablo

我认同获得解决方案的唯一途径是采用以下其中一种方式：

1. 父指针
2. O(n log n) 时间复杂度
3. O(log n) 空间复杂度

- Andrey

Answer 3

正如其他人提到的那样，您无法在常数O(1)空间中解决此问题。此外，目前提出的所有其他解决方案都使用至少O(log^2 n)空间，而不是O(log n)空间：栈具有O(log n)帧，并且每个帧具有O(log n)大小的指针。

现在，@dharm0us当前接受的解决方案通过将BST转换为数组来破坏它。这是不必要的。相反，使用两个迭代器，一个进行顺序遍历，一个进行逆序遍历，并像在数组中一样查找两个数字。每个迭代器都有一个栈，其中每个帧都具有O(log n)大小的指针，总空间为O(log^2 n)。时间明显是线性O(n)。

- Tyson Williams

---

每个迭代器都有一个带有O(log n)帧的堆栈，每个帧都持有一个O(log n)大小的指针，总空间为O(log^2 n)。怎么做？ - Raulp

Tyson，你能解释一下O(log n)大小指针的含义吗？谢谢。 - user674669

@user674669，您的内存中有n个项目。每个内存位置都有一个地址。迭代器必须通过存储内存地址（在像C这样的编程语言中称为指针）来记住它所在的元素。此内存地址的位数必须为Theta(log n)，以便每个项目都具有不同的内存地址。 - Tyson Williams

@TysonWilliams，你好。我引用了你的话，请问你能否详细解释一下你的陈述？ - Raulp

@softy，我的回复对user674669不够吗？ - Tyson Williams