# My passed python solution.

• 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);``````

• 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
``````

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