蠡口116的延续。这道题想了半天想不出递归地做法。于是想到了层次遍历，可以循环地做以下操作：
1）把每层的数据从左到右地放在一个队列里，pop出左边的元素，设为pre；
2）若元素是该层最右非空元素，那不需要做任何操作；否则把pop之后的队首元素作为pre的next；
3）把pre的左右非空孩子依次加入队列，以备下一层的操作；
注意，当前层的元素的最右端的next不是下一层的最左端的，所以每次循环只对当前层的元素赋值，用一个for循环就可以搞定。这道题的解法可以用于蠡口116。
class Solution(object):
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
if root==None: return(None)
q=collections.deque([root])
while q:
size=len(q)
for i in range(size):
pre=q.popleft()
if i<size-1: pre.next=q[0]
if pre.left: q.append(pre.left)
if pre.right: q.append(pre.right)
return(root)
蠡口117. Populating Next Right Pointers in Each Node II
原文：https://www.cnblogs.com/Leisgo/p/11706567.html