如何 link 树中同一级别的所有节点

Question

我有一个二叉树：

struct node 
{
    int n; // value of node
    struct node *left; // left subtree
    struct node *right; // right subtree
    struct node *level; // level pointer (node “to the right”)
}

最初，级别字段设置为 NULL。

我需要编写一个函数来 link 树中同一级别的所有节点（不仅来自示例，还来自任何给定的树）。

void linkSameLevel(struct node *t);

我如何知道我的函数的运行时间和内存使用量对于包含 n 个节点的深度为 d 的树是多少？

这是我的：

这是我需要的：

Answer 1

我想到的最好的事情是你需要使用队列来进行级别顺序遍历。

然后link所有同级节点。关注 link 将提供正确的方向：-

http://www.geeksforgeeks.org/level-order-tree-traversal/

Answer 2

你可以使用两个队列来实现这个目的和BFS遍历。并维护两个指针currNode和prevNode。

在第一季度推送 root。
从 Q1 开始并初始化 prevNode = null。
取自Q1，然后用它初始化currNode。在 Q2 推送 currNode 的子节点。
现在，如果 prev != null，那么 link prevNode 和 currNode。
现在prevNode = currNode.
从第3步开始重复，直到Q1不为空。

当Q1为空时。将 Q2 设置为 Q1，将 Q1 设置为 Q2（这个新的 Q2 将为空）并设置 prevNode = null。转到步骤 3。

void linkSameLevel(node *root)
{
    if (root = null)
        return;
    queue<node *> Q1, Q2;
    Q1.push(root);
    node *currNode; node *prevNode;
    prevNode = null;
    do
    {
        while (!Q1.empty())
        {
            node *currNode = Q1.pop();
            Q2.push(currNode.left); Q2.push(currNode.right);
            if (prevNode != null)
                prevNode.level = currNode;
            prevNode = currNode;
        }
        swap(Q1, Q2);
    } while (!Q1.empty);
}

也看看Level Order Traversal

如何 link 树中同一级别的所有节点

How to link all the nodes at the same level in a tree

c++

binary-tree