AC Java O(n)-time O(1)-space short


  • 2
    E
     public void connect(TreeLinkNode root) {
        TreeLinkNode previous = null;
        TreeLinkNode levelLeftmost = root;
        while (levelLeftmost != null) {
            TreeLinkNode parent = levelLeftmost;
            levelLeftmost = null;
            previous = null;
            while(parent != null) {
                if (levelLeftmost == null) levelLeftmost = parent.left;
                if (levelLeftmost == null) levelLeftmost = parent.right;
                previous = connectNodes(previous, parent.left);
                previous = connectNodes(previous, parent.right);
                parent = parent.next;
            }
        }
     }
     
     private TreeLinkNode connectNodes(TreeLinkNode previous, TreeLinkNode next) {
         if (previous != null) previous.next = next;
         return next == null ? previous : next;
     }

  • 0
    X

    recursive may not be considered as constant space, for there is an implicit stack.


  • 0
    E

    you are right, but the solution can easily be turned to iterative, FTFY


Log in to reply
 

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