LeetCode Populating Next Right Pointers in Each Node II

 // 173ms
 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     int flag;
12     TreeLinkNode *findHead(TreeLinkNode ** q)
13     {
14         TreeLinkNode *p;
15         p=*q;
16              
17         while(p)
18         {
19             if(p->left)
20             {
21                 flag=0;
22                 *q=p;
23                 return p->left; 
24             }
25                 
26             if(p->right)
27             {
28                 flag=1;
29                 *q=p;
30                 return p->right;
31             }
32                 
33             p=p->next;
34         }
35         *q=p;
36         return NULL;
37     }
38     TreeLinkNode *findNext(TreeLinkNode ** q)
39     {
40         TreeLinkNode *p;
41         p=*q;
42         if(*q==NULL)
43             return NULL;
44         if(flag==0&&p->right)  
45         {
46             flag=1;
47             *q=p;
48             return p->right;
49         }
50         if(flag||(flag==0&&p->right==NULL))
51         {
52             p=p->next;
53         }
54         while(p)
55         {
56             if(p->left)
57             {
58                 flag=0;
59                 *q=p;
60                 return p->left; 
61             }
62                 
63             if(p->right)
64             {
65                 flag=1;
66                 *q=p;
67                 return p->right;
68             }
69               
70             p=p->next;
71         }
72         *q=p; 
73         return NULL;
74     }
75     void connect(TreeLinkNode *root) {
76         // Start typing your C/C++ solution below
77         // DO NOT write int main() function
78         TreeLinkNode *p,*q,*t,*tt;
79         if(root==NULL)
80             return;
81         t=root;
82         
83         while(t)
84         {    
85             p=findHead(&t);
86             tt=p;
87             while(q=findNext(&t))
88             {
89                 p->next=q;
90                 p=q;
91             }
92             t=tt;
93         }       
94     }
95 };