使用恒定的额外空间连接同一层级的节点

Question

目标：编写一个函数，将二叉树中同一层的相邻节点连接起来。给定的二叉树节点结构如下。

struct node{
  int data;
  struct node* left;
  struct node* right;
  struct node* nextRight;  
}

最初，所有的nextRight指针指向垃圾值。函数应该为每个节点设置这些指针指向它们的下一个右侧节点。

解决方案：

void connectRecur(struct node* p);
struct node *getNextRight(struct node *p);

// Sets the nextRight of root and calls connectRecur() for other nodes
void connect (struct node *p)
{
    // Set the nextRight for root
    p->nextRight = NULL;

    // Set the next right for rest of the nodes (other than root)
    connectRecur(p);
}

/* Set next right of all descendents of p. This function makes sure that
nextRight of nodes ar level i is set before level i+1 nodes. */
void connectRecur(struct node* p)
{
    // Base case
    if (!p)
       return;

    /* Before setting nextRight of left and right children, set nextRight
    of children of other nodes at same level (because we can access 
    children of other nodes using p's nextRight only) */
    if (p->nextRight != NULL)
       connectRecur(p->nextRight);

    /* Set the nextRight pointer for p's left child */
    if (p->left)
    {
       if (p->right)
       {
           p->left->nextRight = p->right;
           p->right->nextRight = getNextRight(p);
       }
       else
           p->left->nextRight = getNextRight(p);

       /* Recursively call for next level nodes.  Note that we call only
       for left child. The call for left child will call for right child */
       connectRecur(p->left);
    }

    /* If left child is NULL then first node of next level will either be
      p->right or getNextRight(p) */
    else if (p->right)
    {
        p->right->nextRight = getNextRight(p);
        connectRecur(p->right);
    }
    else
       connectRecur(getNextRight(p));
}

/* This function returns the leftmost child of nodes at the same level as p.
   This function is used to getNExt right of p's right child
   If right child of p is NULL then this can also be used for the left child */
struct node *getNextRight(struct node *p)
{
    struct node *temp = p->nextRight;

    /* Traverse nodes at p's level and find and return
       the first node's first child */
    while(temp != NULL)
    {
        if(temp->left != NULL)
            return temp->left;
        if(temp->right != NULL)
            return temp->right;
        temp = temp->nextRight;
    }

    // If all the nodes at p's level are leaf nodes then return NULL
    return NULL;
}

这个解决方案的时间复杂度将会是多少？

- silentseeker

---

你能解释一下你是如何得出这个结论的吗？ - silentseeker

请查看我的回答以获取解释。 - Abhishek Bansal

虽然注释很好，但是那是相当多的代码需要阅读。你可能想学习如何编写伪代码和/或编写足够详细的高级描述。 - Bernhard Barker

请批准正确答案，因为有两个不同的答案。 - Vyshnav Ramesh Thrissur

我在stackoverflow上提供了一个类似问题的答案。 - Tolumide

Answer 1

因为getNextRight的缘故，它是O(n^2)。

最容易看到的是考虑你有一棵完全二叉树。叶子节点的数量是O(n/2)，所以是O(n)。您需要为每个叶子调用getNextRight。

第一个getNextRight将是最右边的最后一个叶子。这不需要通过while循环进行任何传递。

接下来，您为次右侧的倒数第二个叶子调用getNextRight。这需要1次while循环。

对于下一个叶子，您需要通过while循环进行2次操作。等等...您会得到O(1 + 2 + 3 + ... + n/2)，即O(n^2)。

此外，空间复杂度实际上并不是恒定的。如果树是平衡的，则由于递归，它是O(log n)。您可能会有一个log n大小的堆栈。如果树不平衡，情况会更糟。

- andredor

Answer 2

我认为你是从根节点开始逐层连接节点。

在任何一层，由于父节点已经连接，你只需通过父节点到达下一个分支。因此，你最多只访问每个节点一次（或通过子节点访问两次）。

因此，在我看来，时间复杂度的顺序似乎是O(n)，其中n是树中元素的总数。

- Abhishek Bansal

Answer 3

我在stackoverflow上提供了一个类似问题的答案，使用层序遍历。空间和时间复杂度为O(n)。

- Tolumide