algorithm - 平衡二叉树访问

Question

寻找一个就地 O(N) 算法打印节点对(同时遍历树)，如下所示，用于给定的平衡二叉树:

                 a

              b     c

             d e   f g

输出:bc, de, ef, fg

其中“a”是根节点，“b”是左 child ，“c”是右 child ，等等。 请注意输出中的“ef”对。

基于以下评论的附加信息:

1. '节点对'是每个级别的每个相邻对
2. 除了“左”和“右”之外，每个节点还可以有“父”指针/引用
3. 如果我们放宽 O(N) 和就地，是否有更简单的解决方案(包括递归和迭代)？

Answer 1

如果这棵树存储在一个数组中，它可以重新排列为“层级连续”(第一个元素是根，接下来的两个是它的 child ，再接下来的四个是它们的 child ，等等)，问题就很简单了.

如果以其他方式存储，就会出现问题。您可以尝试广度优先遍历，但这会消耗 O(n) 内存。

好吧，我猜你可以通过存储当前级别和当前元素的路径(表示为二进制数)来创建一个 O(n log n) 时间算法，并且只存储最后访问的元素才能创建对。只有 O(1 + log n) 内存。 -> 这实际上可能是一个带有回溯的 O(n) 算法(见下文)。

我知道有一个简单的算法可以在 O(n) 时间内按顺序访问所有节点，因此可能有一个技巧可以在 O(n) 时间内按顺序访问“姐妹”节点。 O(n log n) 时间是有保证的，你可以在给定的级别停止。

还有一个简单的 O(n log n) 算法，您只需过滤给定级别的节点，增加下一个循环的级别。

编辑:

好吧，我创建了一个解决方案，它在 O(n) 中运行，内存为 O(1)(两个机器字大小的变量来跟踪当前和最大级别/技术上是 O(log log n) 内存，但是让我们忽略那个/和一些节点)，但它要求所有节点都包含一个指向其父节点的指针。使用这种特殊结构，可以在没有 O(n log n) 堆栈的情况下进行中序遍历，仅使用两个节点向左、向上或向右步进。你停在一个特定的最高水平，永远不会低于它。您跟踪实际和最大级别，以及您在最大级别遇到的最后一个节点。显然，如果您在最高级别遇到下一个，您可以打印出这样的对。每当您意识到该级别上没有更多内容时，您就会增加最大级别。

从 n-1 节点二叉树中的根节点开始，这相当于 1 + 3 + 7 + 15 + ... + n - 1 次操作。这是 2 + 4 + 8 + 16 + ... + n - log2n = 2n - log2n = O(n) 次操作。

如果没有特殊的 Node* parent 成员，由于中序遍历所需的堆栈，此算法仅适用于 O(log n) 内存。