Solution:: Iterative and Constant space


#1

Comment body goes here./**

  • 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) {}
  • };
    /
    void Solution::connect(TreeLinkNode
    A) {
    struct TreeLinkNode* lm = A;
    while(lm != NULL)
    {
    struct TreeLinkNode *ptr = lm;
    struct TreeLinkNode *lptr = NULL;
    struct TreeLinkNode *fptr = NULL;
    while(ptr != NULL)
    {
    if(lptr == NULL)
    {
    if(ptr->left != NULL)
    {fptr = ptr->left; lptr = ptr->left;}
    else if(ptr->right != NULL)
    {fptr = ptr->right; lptr = ptr->right; ptr = ptr->next;}
    else
    ptr = ptr->next;
    }
    else
    {
    if(ptr->left != NULL && lptr != ptr->left)
    {
    lptr->next = ptr->left;
    lptr = lptr->next;
    }
    if(ptr->right != NULL && lptr != ptr->right)
    {
    lptr->next = ptr->right;
    lptr = lptr->next;
    }
    ptr = ptr->next;
    }
    }
    lm = fptr;
    }
    }