Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

 

For example,

Given the following binary tree,

1       /  \      2    3     / \    \    4   5    7

 

After calling your function, the tree should look like:

1 -> NULL       /  \      2 -> 3 -> NULL     / \    \    4-> 5 -> 7 -> NULL 思路： 对于root，如果存在左右节点则，左节点的next是右节点。如果只存在之一的话，那么那么的next节点是root的next中最左边的节点。注意，因为子节点要用到父节点的next信息，所以先遍历右节点后遍历左节点。 代码：

1     void connect(TreeLinkNode *root) { 2         // IMPORTANT: Please reset any member data you declared, as 3         // the same Solution instance will be reused for each test case. 4         if(root){ 5             if(root->left){ 6                 if(root->right){ 7                     root->left->next = root->right; 8                 } 9                 else{10                     TreeLinkNode *tmp = root->next;11                     while(tmp && !root->left->next){12                         if(tmp->left)13                             root->left->next = tmp->left;14                         else15                             root->left->next = tmp->right;16                         tmp = tmp->next;17                     }18                 }19             }20             if(root->right){21                 TreeLinkNode *tmp = root->next;22                 while(tmp && !root->right->next){23                     if(tmp->left)24                         root->right->next = tmp->left;25                     else26                         root->right->next = tmp->right;27                     tmp = tmp->next;28                 }29             }30             connect(root->right);31             connect(root->left);32         }33     }