O(N) SOLUTION


  • 0
    S

    /**

    • Definition for binary tree with next pointer.

    • struct TreeLinkNode {

    • int val;

    • TreeLinkNode *left, *right, *next;

    • TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}

    • };
      */
      class Solution {
      public:
      void connect(TreeLinkNode *root) {

      if(!root)
      return;
       TreeLinkNode* q[100000];
       int f=0,r=0;
       
       q[r++]=root;
       while(r!=f)
       {
           int i=f,j=r;
           cout<<i<<"\t"<<j;
               
           while(i<j)
           {
             //  cout<<i<<"\t"<<j;
               TreeLinkNode  * t=q[f++];
               if(t->left)
                   q[r++]=t->left;
                   
               if(t->right)
                   q[r++]=t->right;
                   
               i++;
               if(i<j)
                   t->next=q[f];
               else
                   t->next=NULL;
           }
       }
      

      }
      };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.