目录
一、题目内容
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。
示例：
输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
二、解题思路
利用队列，每次出队第一个节点，然后在尾部添加左右节点，除了最后一个出队元素next为None，之前的节点的next都指向出队之后的queue中的第一个元素（右侧节点）。
三、代码
-
"""
-
# Definition for a Node.
-
"""
-
class Node:
-
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
-
self.val = val
-
self.left = left
-
self.right = right
-
self.next = next
-
-
def __repr__(self):
-
return str(self.val)
-
-
-
class Solution:
-
def connect(self, root: 'Node') -> 'Node':
-
-
if not root:
-
return None
-
queue = [root]
-
-
while queue:
-
l = len(queue)
-
for i in range(l):
-
q = queue.pop(0)
-
if q.left:
-
queue.append(q.left)
-
if q.right:
-
queue.append(q.right)
-
if i < l - 1:
-
q.next = queue[0]
-
return root
-
-
-
if __name__ == '__main__':
-
a = Node(1)
-
a.left = Node(2)
-
a.right = Node(3)
-
a.left.left = Node(4)
-
a.left.right = Node(5)
-
a.right.right = Node(7)
-
-
s = Solution()
-
ans = s.connect(a)
-
print(ans)
文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。
原文链接：nickhuang1996.blog.csdn.net/article/details/109094968