Javascript real O(1) solution


  • 2
    D
    function connect(root) {
    	var prev_to_link = null;
    	var next_level_head = null;
    	var curr = root;
    	
    	while (!!curr) {
    		if (!!curr.left) {
    			if (!!prev_to_link) {
    				prev_to_link.next = curr.left;
    			}
    			prev_to_link = curr.left;
    			
    			if (!next_level_head) {
    				next_level_head = curr.left;
    			}
    		}
    		if (!!curr.right) {
    			if (!!prev_to_link) {
    				prev_to_link.next = curr.right;
    			}
    			prev_to_link = curr.right;
    			
    			if (!next_level_head) {
    				next_level_head = curr.right;
    			}
    		}
    		
    		if (!!curr.next) {
    			curr = curr.next;
    		}else {
    			curr = next_level_head;
    			next_level_head = null;
    			prev_to_link = null;
    		}
    	}
    }

  • 0
    J

    Nice try for constant space. However, I have a question. Does the 'next_level_head' record the first node of next level? I think it is.


  • 1
    J

    I just rewrite this method into Java and add some explanations. This method is very intuitive and easy to understand. Thanks for @danielwpz for this nice solution.

    public class Solution {
        public void connect(TreeLinkNode root) {
            
            TreeLinkNode curt = root;
            TreeLinkNode prevNode = null; // previous node. It is used to denote "next"
            TreeLinkNode firstNextLevel = null; // the first node of next level of tree
            
            
            while (curt != null) {
                
                if (curt.left != null) {
                    if (prevNode != null) {
                        prevNode.next = curt.left;
                    }
                    prevNode = curt.left;
                    if (firstNextLevel == null) { // firstNextLevel only need to be assigned once 
                        firstNextLevel = curt.left;
                    }
                }
                
                if (curt.right != null) {
                    if (prevNode != null) {
                        prevNode.next = curt.right;
                    }
                    prevNode = curt.right;
                    if (firstNextLevel == null) {
                        firstNextLevel = curt.right;
                    }
                }
                
                if (curt.next != null) { // when curt.next != null, go to next TreeLinkNode
                    curt = curt.next;
                } else {
                    curt = firstNextLevel; // iterate the next level
                    firstNextLevel = null;
                    prevNode = null;
                }
                
            }
            
        }
    }
    

Log in to reply
 

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