Populating Next Right Pointers in Each Node II <leetcode>

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,

After calling your function, the tree should look like:

         1 -> NULL
       /  
      2 -> 3 -> NULL
     /     
    4-> 5 -> 7 -> NULL

算法：该题和第一个题的变种，不过揭发是一样的，首先也是只要考虑当前节点，然后递归就行了，要点有二：1、当该节点左子树或右子树的右边的第一个节点   2、递归时要先算右子树，因为左子树的处理递归时会用到右边已经形成的结果，代码如下：

 1 /**
 2  * Definition for binary tree with next pointer.
 3  * struct TreeLinkNode {
 4  *  int val;
 5  *  TreeLinkNode *left, *right, *next;
 6  *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     void connect(TreeLinkNode *root) {
12         if(NULL==root)  return;
13         if(NULL!=root->left)
14         {
15              if(NULL!=root->right)
16              {
17                  root->left->next=root->right;
18              }
19              else  root->left->next=find(root->next);
20         }
21         if(NULL!=root->right)
22         {
23             root->right->next=find(root->next);
24         }
25         
26         
27         connect(root->right);
28         connect(root->left);
29     }
30     
31     TreeLinkNode* find(TreeLinkNode *temp)
32     {
33         if(NULL==temp)  return NULL;
34         while(NULL!=temp)
35         {
36             if(NULL!=temp->left)  return temp->left;
37             else if(NULL!=temp->right)  return temp->right;
38             else temp=temp->next;
39         }
40         return NULL;
41     }
42 };