原题
给定一个二叉树
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
说明:
你只能使用额外常数空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
你可以假设它是一个完美二叉树（即所有叶子节点都在同一层，每个父节点都有两个子节点）。
示例:
给定完美二叉树，
1 / \ 2 3 / \ / \ 4 5 6 7
调用你的函数后，该完美二叉树变为：
1 -> NULL / \ 2 -> 3 -> NULL / \ / \ 4->5->6->7 -> NULL
思路
由于题目中常数空间的限制，采用队列的方式对树进行层次遍历是不可行的。
若把问题转化为给定一层已经链接的节点，请链接下面一层，这样问题就迎刃而解了。用start记录当前层的第一个节点，再用cur循环当前层的每个节点。若cur.left存在，则链接cur.left和cur.right；若cur.next存在，则链接cur.right和cur.next.left。下一层的首个节点即start.left，如此循环。
按此思路，代码也就很简单了。
代码
# Definition for binary tree with next pointer.
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
start = root
while start:
cur = start
while cur and cur.left:
cur.left.next = cur.right
if cur.next:
cur.right.next = cur.next.left
cur = cur.next
start = start.left
