0

我在一次采访中被问到这个问题。给出了两个 BST（二叉搜索树）。我们需要以这样一种方式遍历两棵树，以使合并的排序输出成为结果。约束是我们不能像数组那样使用额外的内存。我建议对两棵树进行组合的中序遍历。该方法是正确的，但我陷入了递归，无法编写代码。

注意：我们不能将两棵树合并为一棵。

请有人指导我朝这个方向发展。提前致谢。

4

3 回答 3

0

“最简单”的方法是：

  1. 将树 A 转换为双向链表（已排序）
  2. 将树 B 转换为双向链表（已排序）
  3. 遍历排序列表打印最小值（简单）
  4. 将列表 A 转换为树 A
  5. 将列表 B 转换为树 B

您可以在线找到此步骤的算法。
我认为对树进行并行遍历是不可能的。您将需要其他信息，例如访问标志来消除已访问的左子树，即使这样您也会遇到其他问题。
如果有人知道并行遍历如何实现这一点，我将很高兴知道。

于 2013-02-23T20:57:14.760 回答
0 
print $ merge (inorder treeA) (inorder treeB)

有什么问题？

（注意，上面是实际运行并执行任务的实际 Haskell 代码）。inorder用递归实现是微不足道的。 merge是一个近乎标准的功能，合并它的两个参数有序（非递减）列表，生成有序输出列表，保留重复项。

由于惰性求值和垃圾收集，实际上并没有创建列表 - 每棵树最多保留一个生成的元素，并在生成下一个元素时丢弃，实际上为遍历创建迭代器（每个都有自己的内部状态）。

这是解决方案（如果您的语言不支持上述内容，或等效yield机制，或 Scheme 的显式延续，它允许在每个控制堆栈深处的两个上下文之间切换（因此可以并行进行“两个递归”，如上））：

他们没有说时间复杂度，所以我们可以对第一棵树进行递归遍历，并为第一棵树的每个节点重新遍历第二棵树——同时在第一棵树上保存previous价值。因此，我们在第一棵树上有两个连续的值，并在它们之间打印第二棵树的所有值，使用新的递归遍历，从第二棵树的顶部重新开始，为第一棵树的每对新值。

于 2013-02-23T22:52:56.687 回答
0

我假设树中没有指向父节点或下一个节点的链接，否则这将很容易：您只需按照这些链接迭代您的树并编写您的合并算法，就像您对链表一样。

如果您没有下一个或父链接，则无法编写简单的递归。您将需要两个“递归”堆栈。您可以实现以下结构，它允许您分别迭代每个树。

class Iterator
{
    stack<Node> st;
    int item(){
       return st.top().item();
    }
    void advance(){
        if (st.top().right != null)
            st.push(st.top().right);
            // Go as far left as possible
            while (st.top().left != null) st.push(st.top().left);
        else {
            int x = st.top().item();
            // we pop until we see a node with a higher value
            while(st.top().item()<=x) st.pop(); 

        }
    }
};

然后使用其中两个迭代器编写合并算法。

您将需要 O(log n) 空间，但渐近地说，这只不过是任何递归迭代。

于 2013-02-23T21:25:43.670 回答