O(1) space complexity, O(n) time complexity solution with comments and explanation


  • 0
    W

    The idea is to have a pointer to the previous level so we can build the linkedlist for current level. See code below, has lots of comments for explanation.
    Solution runs in 1ms if I remove all the comments

    public void connect(TreeLinkNode root) {
          if (root == null) return;
          if (root.left != null) { root.left.next = root; root.right.next = root; }
          TreeLinkNode currHead = root.left, curr = currHead;
            
          /**
           * 1) If current is a left child, set curr.next to right child
           * 2) If current is a right child, set curr.next to parent.next.left child
           * 3) Set the childs next pointer to parent
           * 4) If curr == null, go to next level and continue with (1)
           */
          while (curr != null) {
              TreeLinkNode parent = curr.next;
              
              if (parent.right == curr) {
                  //curr is a right child, so set to parent.next.left
                  if (parent.next != null) curr.next = parent.next.left;
                  else curr.next = null;
              } else {
                  //curr is a left child, so set to parent.right
                  curr.next = parent.right;
              }
                
              //set child's next pointer to curr
              if (curr.left != null) { curr.left.next = curr; curr.right.next = curr; }
              
              //Advance to next node
              curr = curr.next;
              
              //If we are at the end of the current level, go to next level
              if (curr == null) {
                  curr = currHead.left;
                  currHead = curr;
              }
          }
    }
    

Log in to reply
 

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