Advertisement
HjHimansh

Populating Next Right Pointers in Each Node II

Jan 5th, 2021
1,071
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     Node* left;
  7.     Node* right;
  8.     Node* next;
  9.  
  10.     Node() : val(0), left(NULL), right(NULL), next(NULL) {}
  11.  
  12.     Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
  13.  
  14.     Node(int _val, Node* _left, Node* _right, Node* _next)
  15.         : val(_val), left(_left), right(_right), next(_next) {}
  16. };
  17. */
  18.  
  19. class Solution {
  20. public:
  21.    
  22.    
  23.     Node* connect(Node* root) {
  24.         if(!root)   return root;
  25.         root->next = nullptr;
  26.         Node *parentLeftMost = root;
  27.         //parent level is sorted
  28.        
  29.         while(1){
  30.             while(parentLeftMost && !parentLeftMost->left && !parentLeftMost->right){
  31.                 parentLeftMost = parentLeftMost->next;
  32.             }
  33.             if(!parentLeftMost){
  34.                 //i.e there is no next level
  35.                 return root;
  36.             }
  37.             Node *upcomingParentLeftMost = parentLeftMost->left ? parentLeftMost->left : parentLeftMost->right;  //refers to the leftmost node of next level. Will be the next parentLeftMost
  38.  
  39.             Node *tempP = parentLeftMost;
  40.             Node *tempC = upcomingParentLeftMost;
  41.             while(1){
  42.  
  43.                 Node *toAttach = nullptr;
  44.                 if(tempP->right != nullptr && tempP->right!= tempC){
  45.                    toAttach = tempP->right;
  46.                 }
  47.                 else{
  48.                     while(tempP->next != nullptr && toAttach == nullptr){
  49.                         tempP = tempP->next;
  50.                         toAttach = tempP->left ? tempP->left : tempP->right;
  51.                     }
  52.                 }
  53.                 tempC->next = toAttach;
  54.                 tempC = tempC->next;
  55.                 if(tempC == nullptr){
  56.                     parentLeftMost = upcomingParentLeftMost;
  57.                     break;
  58.                 }
  59.             }
  60.         }
  61.     }
  62. };
Advertisement
RAW Paste Data Copied
Advertisement