给定一个二叉树
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
