题目描述：
题解一：层序遍历 通过
1.对二叉树进行层序遍历（通过借助队列实现），将各个节点按照层序遍历结果保存在list中。
2.将每层层序遍历结果中除了最后一个节点的next设置为当前层下一个节点，最后一个节点的next设置为None。
class Solution(object):
def connect(self, root):
noderes = []
layers = []
if root==None:
return root
layer = []
layer.append(root)
noderes.append(layer)
while noderes:
nowlayer = noderes[0]
noderes.remove(nowlayer)
layers.append(nowlayer)
newlayer = []
for node in nowlayer:
if node.left:
newlayer.append(node.left)
if node.right:
newlayer.append(node.right)
if len(newlayer)>0:
noderes.append(newlayer)
for eachlayer in layers:
for i in range(len(eachlayer)-1):
eachlayer[i].next = eachlayer[i+1]
eachlayer[-1].next = None
return root
题解二：递归
参考https://blog.csdn.net/qq_32424059/article/details/90487297
1.如果root左右子节点都存在，left.next则为右子节点，right.next为root.next的子节点（左子节点如果存在则为左子节点，否则为右子节点，如果都不存在，则找到root.next.next，如果都不存在则填充为None）
2.因此创建一个函数findcousin(node,parent) ，node为parent的子节点，该函数试图在root的cousin节点中找到一个有子节点的，并将node.next设置为该cousin节点的左子节点（如果存在）或右子节点。
3.如果root 左右子节点均存在，left.next即为right，然后对root.right调用findcousin，如果只有left，则对left调用findcousin，如果只有right，则对right调用。
4.对root的左右子树调用connect，需要先对right进行处理，因为findcousin需要用到该层当前节点之后的信息。
class Solution(object):
def connect(self, root):
if root==None:
return root
def findcousin(node,parent):
tmp = parent.next
while tmp:
if tmp.left:
node.next = tmp.left
break
elif tmp.right:
node.next = tmp.right
break
tmp = tmp.next
if root.left and root.right:
root.left.next = root.right
findcousin(root.right,root)
elif root.left:
findcousin(root.left,root)
elif root.right:
findcousin(root.right,root)
self.connect(root.right)
self.connect(root.left)
return root
