c++ - 连接二叉树同一层的节点

Question

我看过一些关于如何连接同一级别的二叉树节点的文章/页面，但这些文章都没有清楚地解释过程/算法。如果有人可以解决这个问题，我将不胜感激。代码不是必需的，但用伪代码解释它会很好。

为了便于讨论，让我们将树视为:

               0
           1        2
        3     4   5    6
    7                      9

在上面的例子中:

0 should point to null.
1 should point to 2.
3 should point to 4.
....
7 should point to 9.
9 should point to NULL.

基本的树结构是:

class Tree {
  public:
    int data;
    Tree* left;
    Tree* right;
    Tree* next;
}

Answer 1

有一种不使用额外内存的有趣方法，这有点归纳:

1. 第一层已经连接(只有一个节点)

2. 假设 i 层已连接。然后连接级别 i+1 执行以下操作:

   a) 将节点lst(只是我们稍后会用到的中间变量)初始化为null

   b) 从 i 层的第一个节点开始。

   c) 从第一个节点开始遍历 i 层上的节点。请注意，您可以轻松遍历级别 i 上的节点，因为它已经连接，因此您在每个节点中都有兄弟指针。

   d) 对于层 i 上的每个节点，首先查看其左子节点，然后查看其右子节点。对于每个不为 null 的 child ，如果 lst 不为 null，则将 lst 连接到该 child 。然后将 lst 设置给那个 child 。

一旦你连接了关卡i + 1，你就可以进入下一个关卡。如果在遍历该级别后 lst 仍然为 null，则意味着该级别上没有节点有子节点 => 这是最后一个级别，您可以停止算法。

很容易说明为什么会这样，它需要线性时间和常量空间，因此它严格来说优于带队列的 BFS(需要线性内存)。