LeetCode

Populating Next Right Pointers in Each Node II

2014.1.8 21:00

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

Solution:

　　This problem is a variation from Populating Next Right Pointers in Each Node. The difference is that the tree needn't be perfect.

　　Solution is similar. The left node is next to the right node, and the right node is next to the leftest node right to it.

　　Time and space complexities are both O(n), where n is the number of nodes in the tree.

Accepted code:

 1 // 1WA, 1AC, the first attempt is wrong, only works for perfect binary trees
 2 /**
 3  * Definition for binary tree with next pointer.
 4  * struct TreeLinkNode {
 5  *  int val;
 6  *  TreeLinkNode *left, *right, *next;
 7  *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     void connect(TreeLinkNode *root) {
13         // IMPORTANT: Please reset any member data you declared, as
14         // the same Solution instance will be reused for each test case.
15         if(root == nullptr){
16             return;
17         }
18         
19         TreeLinkNode *pp;
20         
21         // search the next pointer from left to right
22         pp = root->next;
23         while(pp != nullptr){
24             if(pp->left != nullptr){
25                 pp = pp->left;
26                 break;
27             }
28             if(pp->right != nullptr){
29                 pp = pp->right;
30                 break;
31             }
32             pp = pp->next;
33         }
34         
35         if(root->right != nullptr){
36             root->right->next = pp;
37         }
38         
39         if(root->left != nullptr){
40             root->left->next = (root->right != nullptr) ? root->right : pp;
41         }
42         
43         // since the searching of next pointer is from left to right
44         // the recursion must be done from right to left 
45         connect(root->right);
46         connect(root->left);
47     }
48 };