题目:
给定一个二叉树
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
分析:
- 采用BFS遍历,每一层遍历后,遍历节点列表,列表中前一节点next指针指向后一节点
代码:
class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
nodes = [root]
while nodes:
temp = []
for x in nodes:
if x:
if x.left: temp.append(x.left)
if x.right: temp.append(x.right)
for i,y in enumerate(temp[:-1]):
y.next = temp[i + 1]
nodes = temp
思考: