populating next pointer I II

populating next pointer I II

I easy problem

This is not hard, because it is a full binary tree.

`````` 1 /**
2  * Definition for binary tree with next pointer.
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:
12         if ( !root ) {
13             return;
14         }
15         if ( root->left ) {
16             root->left->next = root->right;
17         }
18         if ( root->right ) {
19             if ( root->next ) {
20                 root->right->next = root->next->left;
21             }
22         }
23         connect(root->left);
24         connect(root->right);
25     }
26 };``````

II a little hard

I was trying to resolve this problem by recursive way, but I failed. This problem should be resolved by level travel the tree.

`````` 1 /**
2  * Definition for binary tree with next pointer.
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:
12         if ( !root ) {
13             return;
14         }
15         queue < pair< TreeLinkNode*, int > > Q;
16         while ( !Q.empty() ) {
17             Q.pop();
18         }
20         while ( !Q.empty() ) {
21             auto p = Q.front();
22             Q.pop();
23             if ( Q.empty() || p.second != Q.front().second ) {
24                 p.first->next = NULL;
25             } else {
26                 p.first->next = Q.front().first;
27             }
28             if ( p.first->left ) {
29                 Q.push(pair < TreeLinkNode*, int >(p.first->left,p.second+1));
30             }
31             if ( p.first->right ) {
32                 Q.push(pair < TreeLinkNode*, int >(p.first->right,p.second+1));
33             }
34         }
35     }
36 };``````