# # 【LeetCode】117. Populating Next Right Pointers in Each Node II 解题报告（Python）

## # 题目描述：

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.

For example,

``````Given the following binary tree,

1
/  \
2    3
/ \    \
4   5    7

After calling your function, the tree should look like:

1 -> NULL
/  \
2 -> 3 -> NULL
/ \    \
4-> 5 -> 7 -> NULL
``````

## # 解题方法

【LeetCode】116. Populating Next Right Pointers in Each Node 解题报告（Python）open in new window很像，只不过这个题没有完全二叉树的条件，因此我们需要额外的条件。

``````# Definition for binary tree with next pointer.
#     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
queue = collections.deque()
queue.append(root)
while queue:
_len = len(queue)
for i in range(_len):
node = queue.popleft()
if i < _len - 1:
node.next = queue[0]
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
``````

constant extra space.

## # 日期

2018 年 3 月 14 日 --霍金去世日