二叉树中相同深度的链接节点

Question

给你一个class节点

public class Node {
    Node left;
    Node right;
    Node next;
}

现在给定一个节点，它是一棵二叉树的根节点（不是完全二叉树，有些节点只有左或右child），你需要设置next树中所有 Nodes 的字段，以便相同深度的所有 Nodes 在链表中从左到右连接。

并且您不应该使用线性数量的附加内存，例如用深度注释每个节点。这意味着 class Node 中没有像 int depth 这样的额外字段或类似的意图，例如地图 Map<Node, Integer>.

如果我可以设置节点深度并在树上进行 BFS 遍历，我可以很容易地解决这个问题。当当前节点和前一个节点处于同一深度时，我为前一个节点设置 next。

但是，面试官要求我不要注释每个节点的深度。请帮我解决这个问题。谢谢。请告诉我运行时间对于 non-annotating 解决方案是否仍然是 O(n)。

Answer 1

我假设您知道树的高度 h（可以在 O(n) 时间和对数 space 中计算）。通过维护所有 h 列表的尾部，您可以使用 DFS 生成列表。您只需要存储 h 个尾部元素和调用堆栈参数（O(log n) 附加 space）：

初始化：

listTails := array with h null entries (type Node)
n := root
depth := 0

并调用：

function buildLists(Node n, int depth, Node[] listTails)
{
    if(n == null)
        return;

    if(listTails[depth] != null)
        listTails[depth].next = n;
    listTails[depth] = n;

    buildLists(n.left, depth + 1, listTails);
    buildLists(n.right, depth + 1, listTails);
}

如果您为列表尾部使用动态大小的数据存储（例如 C++ 中的 std::vector<>），甚至不需要事先知道 h。

这实质上是在整棵树中从左到右传播一个前沿。

二叉树中相同深度的链接节点

Linking node at the same depth in a binary tree

algorithm

tree