把binary tree多增加一個next pointer，指去它的右邊鄰居，可以隔空指去遠方- 如果中間都是NULL、沒有node的話 。
感覺寫的有點醜！！！是不是有漂亮一點的寫法！！！
似乎最快的方法是stack 把東西存起來嗎？！
但題目明明說要用constant space ?! 啊不管它了啊啊啊啊啊
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *left;
* struct Node *right;
* struct Node *next;
* };
*/
struct Node* findNext(struct Node* ptr)
{
if (ptr->next !=NULL)
{
if (ptr->next->left !=NULL)
return ptr->next->left;
else if (ptr->next->right !=NULL)
return ptr->next->right;
return (findNext(ptr->next));
}
return NULL;
}
struct Node* connect(struct Node* root) {
if (root==NULL)
return NULL;
if (root->left != NULL && root->right !=NULL)
{
root->left->next =root->right;
root->right->next= findNext(root);
}
else if (root->left==NULL && root->right == NULL)
{
return root;
}
else if (root->left==NULL && root->right !=NULL)
{
root->right->next= findNext(root);
}
else //if (root->left != NULL && root->right ==NULL)
{
root->left->next = findNext(root);
}
connect(root->right);
connect(root->left);
return root;
}
沒有留言:
張貼留言