My passed python solution.


  • 0
    L

    Here is the code, the key is parse right, then parse left.

    class Solution:
    # @param root, a tree node
    # @return nothing
    def connect(self, root):
        def getNext(node):
            p=node;
            while(p.next!=None):
                if(p.next.left!=None):
                    return p.next.left;
                if(p.next.right!=None):
                    return p.next.right;
                p=p.next;
            return None;
        
        def connectCore(root):
            if(root==None or (root.left == None and root.right==None)):return;
            else:
                if(root.right!=None):
                    root.right.next=getNext(root);
                    connectCore(root.right);
    
                if(root.left!=None): #right is None.try find by parent
                    if(root.right!=None):
                        root.left.next=root.right;
                    else:
                        root.left.next=getNext(root);
                    connectCore(root.left);
        connectCore(root);

  • 0
    D

    my code can run at the first problem and this problem.It's not used O(1) memory. But system accepted it .
    I think My code used memory will less than recursive. Below is my code:

    def connect(self, root):
        quene = []
        if root == None:
            return 
        quene.append((0,root))
        fatherDeep = -1
        leftNode = None
        while quene != [] :
            currentDeep, node = quene.pop(0)
            if node.left != None:
                quene.append((currentDeep+1, node.left))
            if node.right != None:
                quene.append((currentDeep+1, node.right))
            if currentDeep != fatherDeep:
                fatherDeep = currentDeep
            else:
                leftNode.next = node
            leftNode = node
    

Log in to reply
 

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