目标:编写一个函数,将二叉树中同一层的相邻节点连接起来。给定的二叉树节点结构如下。
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;
}
这个解决方案的时间复杂度将会是多少?