9 - Medium - 每个节点的右向指针

给定一个二叉树

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

利用层序遍历的结果，其中遍历结果列表中存储具体节点，且空节点也要存

# 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:
    def connect(self, root):
        if not root:
            return
        level = []
        self.dfs(root, 0, level)
        for i in range(len(level)):
            length = len(level[i])
            for j in range(length):
                if level[i][j]:
                    if j == length-1:
                        level[i][j].next = None
                    else:
                        level[i][j].next = level[i][j+1]

    def dfs(self, root, depth, res):
        if len(res) < depth+1:
            res.append([])
        if root == None:
            res[depth].append(None)
            return res
        res[depth].append(root)
        self.dfs(root.left, depth+1, res)
        self.dfs(root.right, depth+1, res)

# 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):
        if not root:
            return None
        root.next = None
        pre_next = root
        cur_next = root.left
        while root.left:
            cur_next.next = pre_next.right
            cur_next = cur_next.next
            while pre_next.next:
                cur_next.next = pre_next.next.left
                cur_next = cur_next.next
                cur_next.next = pre_next.next.right
                cur_next = cur_next.next
                pre_next = pre_next.next
            cur_next.next = None
            root = root.left
            pre_next = root
            cur_next = root.left