Another accepted Java solution


  • 2

    The idea is to use next pointer to traverse at each level, and call getNext(root) to get the left most node at the next level.

    public static class Solution {
        
        public void connect(TreeLinkNode root) {
          while (root != null) {
            TreeLinkNode curr = root;
            
            // level traversal
            while (curr != null) {
              if (curr.left != null) {
                curr.left.next = curr.right != null ? curr.right : getNext(curr);
              }
              
              if (curr.right != null) {
                curr.right.next = getNext(curr);
              }
              
              curr = curr.next;
            }
            
            // next level
            if (root.left != null) {
              root = root.left;
            } else if (root.right != null) {
              root = root.right;
            } else {
              root = getNext(root);
            }
          }
        }
        
        TreeLinkNode getNext(TreeLinkNode node) {
          TreeLinkNode next = node.next;
          
          while (next != null) {
            if (next.left != null) return next.left;
            if (next.right != null) return next.right;
            next = next.next;
          }
          
          return null;
        }
        
      }

Log in to reply
 

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