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.
 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 ( !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.
 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 ( !root ) {
13             return;
14         }
15         queue < pair< TreeLinkNode*, int > > Q;
16         while ( !Q.empty() ) {
17             Q.pop();
18         }
19         Q.push(pair< TreeLinkNode*, int >(root,0));
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 };

Loading Disqus comments...
Table of Contents