gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:54:10 26 4
gpt4 key购买 nike

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

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

               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;
}

最佳答案

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

  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(需要线性内存)。

关于c++ - 连接二叉树同一层的节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41690862/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com