# A non-recursion and constant space cost AC solution

• The idea is very simple.
Parent is the first node of current level, and during the while, visited each node of current level by parent=parent.next
During each while, first visit the left child, if the right child is not None, then the parent.left.next=parent.right.
Othervise, visited the parent next, and find the first child node that is not None.
The next node of right child can be found in the same way.
At the end, if parent.next is None, it means we have already find all the children's next node of current level. Then we should set first node of next level as parent for next while.

``````class Solution:
# @param root, a tree node
# @return nothing
def connect(self, root):
next_start=[]
parent=root
while None != parent:
if None != parent.left:
if len(next_start) == 0:
next_start=[parent.left]
if None != parent.right:
parent.left.next=parent.right
else:
parent_next=parent.next
tmp_next=None
while None != parent_next:
tmp_next=parent_next.left if None != parent_next.left else parent_next.right
if None != tmp_next:
break
parent_next=parent_next.next
parent.left.next=tmp_next
if None != parent.right:
if len(next_start) == 0:
next_start=[parent.right]
parent_next=parent.next
tmp_next=None
while None != parent_next:
tmp_next=parent_next.left if None != parent_next.left else parent_next.right
if None != tmp_next:
break
parent_next=parent_next.next
parent.right.next=tmp_next
parent=parent.next
if None == parent and 0 < len(next_start):
parent=next_start[0]
next_start=[]
return``````

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