Populating Next Right Pointers in Each Node II

Obviously, the thought of this question is also disturbed by the former one. First, post the wrong code:

/** 
 * 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->left;  
                break;  
            }  
            if(rt->right!=NULL){  
                nextnode=rt->right;  
                break;  
            }  
            rt=rt->next;  
        }  
        if(root->right!=NULL){  
            root->right->next=nextnode;  
            if(root->left!=NULL)  
                root->left->next=root->right;  
        }  
        else if(root->left!=NULL)  
            root->left->next=nextnode;  
  
        connect(root->right);  
        connect(root->left);  
    }  
};

补充：软件开发 , C++ ,