/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
// Note: The Solution object is instantiated only once and is reused by each test case.
TreeLinkNode *tmp;
if(root==NULL) return;
if(root->left!=NULL){
if(root->right!=NULL)
root->left->next=root->right;
else{
tmp=root->next;
while(tmp!=NULL){
if(tmp->left!=NULL){
root->left->next=tmp->left;
break;
}
if(tmp->right!=NULL){
root->left->next=tmp->right;
break;
}
tmp=tmp->next;
}
}
}
if(root->right!=NULL){
tmp=root->next;
while(tmp!=NULL){
if(tmp->left!=NULL){
root->right->next=tmp->left;
break;
}
if(tmp->right!=NULL){
root->right->next=tmp->right;
break;
}
tmp=tmp->next;
}
}
connect(root->left);
connect(root->right);
}
};
Input:
{2,1,3,0,7,9,1,2,#,1,0,#,#,8,8,#,#,#,#,7}
Output:
{2,#,1,3,#,0,7,9,1,#,2,1,0,#,7,#}
Expected:
{2,#,1,3,#,0,7,9,1,#,2,1,0,8,8,#,7,#}
Take notice that:
connect(root->left);
connect(root->right);
The traversal is DFS, therefore, the right part of some layer has been linked. For example, 0->7->9....1 has formed when visiting 7:1->0. However, the next hop of 0 couldn't be linked because 9-->1 hasn't been connected. So the the right code is:
[cpp] view plaincopy
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
// Note: The Solution object is instantiated only once and is reused by each test case.
TreeLinkNode *tmp,rt,curnode;
if(root==NULL) return;
rt=root;
while(rt!=NULL){
if(rt->
left!=NULL){
curnode=rt->left;
break;
}
if(rt->right!=NULL){
curnode=rt->right;
break;
}
rt=rt->next;
}
if(root->left!=NULL){
if(root->right!=NULL)
root->left->next=root->right;
else{
tmp=root->next;
while(tmp!=NULL){
if(tmp->left!=NULL){
root->left->next=tmp->left;
break;
}
if(tmp->right!=NULL){
root->left->next=tmp->right;
break;
}
tmp=tmp->next;
}
}
}
if(root->right!=NULL){
tmp=root->next;
while(tmp!=NULL){
if(tmp->left!=NULL){
root->right->next=tmp->left;
break;
}
if(tmp->right!=NULL){
root->right->next=tmp->right;
break;
}
tmp=tmp->next;
}
}
connect(root->right);
connect(root->left);
}
};
A concise code could be written as:
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
// Note: The Solution object is instantiated only once and is reused by each test case.
TreeLinkNode *rt=NULL,*nextnode=NULL;
if(root==NULL) return;
rt=root->next;
while(rt!=NULL){
if(rt->left!=NULL){
nextnode=rt