O(1) space O(n) complexity Iterative Solution


  • 267
    F

    Just share my iterative solution with O(1) space and O(n) Time complexity

    public class Solution {
        
        //based on level order traversal
        public void connect(TreeLinkNode root) {
    
            TreeLinkNode head = null; //head of the next level
            TreeLinkNode prev = null; //the leading node on the next level
            TreeLinkNode cur = root;  //current node of current level
    
            while (cur != null) {
                
                while (cur != null) { //iterate on the current level
                    //left child
                    if (cur.left != null) {
                        if (prev != null) {
                            prev.next = cur.left;
                        } else {
                            head = cur.left;
                        }
                        prev = cur.left;
                    }
                    //right child
                    if (cur.right != null) {
                        if (prev != null) {
                            prev.next = cur.right;
                        } else {
                            head = cur.right;
                        }
                        prev = cur.right;
                    }
                    //move to next node
                    cur = cur.next;
                }
                
                //move to next level
                cur = head;
                head = null;
                prev = null;
            }
            
        }
    }

  • 0
    W
    This post is deleted!

  • 1
    S

    +1 for a genuine O(1) space solution with elegant implementation


  • 1
    S

    This code is really elegant. Logic is great.!


  • 1
    R

    great solution. one minor thing is that I think the head and prev can be placed inside the outer while loop.


  • 58
    R

    I did some modification to increase its readability.

    public class Solution {
    
        public void connect(TreeLinkNode root) {
            TreeLinkNode head=root;//The left most node in the lower level
            TreeLinkNode prev=null;//The previous node in the lower level
            TreeLinkNode curr=null;//The current node in the upper level
            while (head!=null){
                curr=head;
                prev=null;
                head=null;
                while (curr!=null){
                    if (curr.left!=null){
                        if (prev!=null)
                            prev.next=curr.left;
                        else 
                            head=curr.left;
                        prev=curr.left;
                    }
                    if (curr.right!=null){
                        if (prev!=null)
                            prev.next=curr.right;
                        else 
                            head=curr.right;
                        prev=curr.right;
                    }
                    curr=curr.next;
                }
            }
        }
    }

  • 0
    G

    Shouldn't we see whether head is NULL before assign new value ?


  • 0
    S

    @gaopeng Because while (cur != null) did the same thing.


  • 35
    J

    My solution is similar, it's basicly a level BFS without using additional qeue, as the next link already serves the queue functionality..

    The difference of my solution is to introduce a dummy head node, which can save some if/else when dealling the first element in the list.

       public class Solution {
          	public static void connect(TreeLinkNode root) {
        		TreeLinkNode nextHead = new TreeLinkNode(0);
        		nextHead.next = root;
        		while(nextHead.next != null){
        			TreeLinkNode tail = nextHead;
        			TreeLinkNode n = nextHead.next;
        			nextHead.next = null;
        			for(; n != null; n = n.next){
        				if(n.left != null){
        					tail.next = n.left;
        					tail = tail.next;
        				}
        				
        				if(n.right != null){
        					tail.next = n.right; 
        					tail = tail.next;
        				}
        			}
        		}
        	}
        }

  • 4
    P

    Check out my solution :)

    void connect(TreeLinkNode *root) {
        if (root == NULL) return;
        TreeLinkNode * start = root;//start of cur level
        TreeLinkNode * end = root;//end of all levels
        TreeLinkNode * levelEnd = root;//cur level's end
        while (start != NULL)
        {
            if (start->left != NULL)
            {
                end->next = start->left;
                end = end->next;
            }
            if (start->right != NULL)
            {
                end->next = start->right;
                end = end->next;
            }
            if (start == levelEnd)
            {
                start = start->next;//start points to next level
                levelEnd->next = NULL;//set cur level's next to NULL
                levelEnd = end;//set cur level's end as next level's end
            }
            else
            {
                start = start->next;
            }
        }
    }

  • 0
    R
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info.


  • 1
    S

    can you explain why is the time complexity O(n)? I think it's O(n*logn)


  • 0
    J

    For each node, we traverse its 2 children. So 2*n times totally, O(n) time complexity.


  • 0
    J

    After traverse one layer, how did you jump to the next layer? Could you please explain that?


  • 0
    J

    OK I know that now. nextHead.next always points to the first node of the next layer.


  • 0
        public static void connect(TreeLinkNode root) {
    		if(root==null) return;
    		TreeLinkNode current = root;
    		TreeLinkNode nextLevel = (root.left!=null)?root.left:root.right;
    		while(nextLevel!=null) {
    			TreeLinkNode currChild = new TreeLinkNode(0);
    			nextLevel = null;
    			while(current!=null) {
    				if(current.left!=null || current.right!=null) {
    					if(nextLevel==null) nextLevel = (current.left!=null)?current.left:current.right;
    					if(current.left!=null) {
    						currChild.next = current.left;
    						currChild = currChild.next;
    					}
    					if(current.right!=null) {
    						currChild.next = current.right;
    						currChild = currChild.next;
    					}
    				}
    				current=current.next;
    			}
    			current=nextLevel;
    		}
    	}
    

    My solution O(1) space, O(n) time


  • 10
    B
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        TreeLinkNode dummy = new TreeLinkNode(0);
        dummy.next = root;
        while (dummy.next != null) {
            TreeLinkNode cur = dummy.next, pre = dummy;
            dummy.next = null;
            while (cur != null) {
                if (cur.left != null)
                    pre = pre.next = cur.left;
                if (cur.right != null)
                    pre = pre.next = cur.right;
                cur = cur.next;
            }
        }
    }

  • 0

    The idea of using a nextHead node is really clever!


  • 1

    Wow, concise code!


Log in to reply
 

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