Simple solution using constant space


  • 143
    D

    The idea is simple: level-order traversal.
    You can see the following code:

    public class Solution {
        public void connect(TreeLinkNode root) {
            
            while(root != null){
                TreeLinkNode tempChild = new TreeLinkNode(0);
                TreeLinkNode currentChild = tempChild;
                while(root!=null){
                    if(root.left != null) { currentChild.next = root.left; currentChild = currentChild.next;}
                    if(root.right != null) { currentChild.next = root.right; currentChild = currentChild.next;}
                    root = root.next;
                }
                root = tempChild.next;
            }
        }
    }

  • 3
    L

    Really simple solution. But it may not using constant space. Since you create a new node at every level, the space complexity should be O(log(n)).
    Any way, I think it is the simplest solution. :)
    If you program in C++, you may could free the new node after the inner while loop.


  • 0
    U

    I agree with liranjiao. It is not a o(1) solution.


  • 16
    G

    not necessary to create new node every level. you can create it at the beginning and keep reusing it.


  • 1
    N

    tempChild.next = null;......instead of creating one


  • 1

    Smart code.

    And for each level, tempChild is just like to add a dummy head to a list.


  • 0
    Y

    Actually, no need to use new, because no need to keep any information in the heap.
    TreeLinkNode tempChild = TreeLinkNode(0); is also correct.


  • 35
    A

    A very minor modification to use only one extra temporary node, rather than creating a new temporary node every level.

    public void connect(TreeLinkNode root) {
        TreeLinkNode tempChild = new TreeLinkNode(0);
        while (root != null) {
            TreeLinkNode currentChild = tempChild;
            while (root != null) {
                if (root.left != null) {
                    currentChild.next = root.left;
                    currentChild = currentChild.next;
                }
                if (root.right != null) {
                    currentChild.next = root.right;
                    currentChild = currentChild.next;
                }
                root = root.next;
            }
            root = tempChild.next;
            tempChild.next = null;
        }
    }

  • 1
    K

    can you explain this: root = tempChild.next;


  • 0
    H
    This post is deleted!

  • 0
    H

    tempChild is dummy head of root's next level. So root = tempChild.next moves to loop next level's nodes.


  • 1
    Z

    can you exlplain little more?still confused...the root=tempChild.next


  • 3
    L

    root is the head of each level. here is the one with comments

    public void connect(TreeLinkNode root) {
        TreeLinkNode head=root,tmpNode=new TreeLinkNode(0);
        //loop the head in the level
        while(head!=null){
        	//loop the node in each level
        	TreeLinkNode node=head,child=tmpNode;
        	while(node!=null){
        		if(node.left!=null){
        			child.next=node.left;
        			child=node.left;
        		}
        		if(node.right!=null){
        			child.next=node.right;
        			child=node.right;
        		}
        		node=node.next;
        	}
        	head=tmpNode.next;
        	tmpNode.next=null;
        }         
    }

  • 0
    D

    agreed with yutao.
    it's ok to create a new TreeLinkNode during each loop because it lives within current loop.


  • 13
    C

    I think the explanation should be, when "TreeLinkNode currentChild = tempChild;" the currentChild is the address of the object, so every change to currentChild is the change to tempChild. So in the following two if(){}..., because of "currentChild.next = root.right;" or"currentChild.next = root.right;" the tempChild.next is change into the first node of this level. However, because of "currentChild = currentChild.next;" the currentChild change to the address of another object. So the tempChild will not change with it anymore and it will stay on the first node of this level. I think that's why tmpNode.next is the first node of each level. Am I correct


  • 0
    X

    @cx.guooutlook.com The underlying mechanics between Java and C++ are quite different. Even now, I am still confused whether Java is pass by value or reference.


  • 0
    S

    @cx.guooutlook.com
    really appreciate your detailed explanation!


  • 0
    M
    This post is deleted!

  • 1
    H

    @gzproger i think what u said is wrong. For ex, {1,2}. tempChild->next will always point to 2, which will cause infinite loop.....


  • 0
    X

    Here's my Python version with slight modification to make O(1) space.

    class Solution:
        # @param root, a tree link node
        # @return nothing
        def connect(self, root):
            sentinel = TreeLinkNode(0)
            while root:
                curChild = sentinel
                while root:
                    if root.left:
                        curChild.next = root.left
                        curChild = curChild.next
                    if root.right:
                        curChild.next = root.right
                        curChild = curChild.next
                    root = root.next
                root = sentinel.next
                sentinel.next = None
    

Log in to reply
 

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