给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
提示：
树中节点的数量少于 4096
-1000 <= node.val <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
python
# 0116.填充每个节点的下一个右侧节点指针
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
class Solution:
def connect(self, root: Node) -> Node:
"""
迭代法, list解法
:param root:
:return:
"""
if not root:
return None
queue = [root]
while queue:
n = len(queue)
for i in range(n):
node = queue.pop(0)
if node.left: # 添加节点的左子节点入队
queue.append(node.left)
if node.right: # 添加节点的右子节点入队
queue.append(node.right)
if i == n-1: # 当前层的最后节点时
break
# 添加next指针，指向下个右侧节点，如当层序号1->2->3->4->...->n->None，每个节点指针默认None
node.next = queue[0]
return root
class Solution1:
def connect(self, root: Node) -> Node:
"""
迭代法，链表解法
:param root:
:return:
"""
first = root
while first:
cur = first
while cur: # 遍历每层节点
if cur.left: # 左节点next
cur.left.next = cur.right
if cur.right and cur.next: # 右节点的next
cur.right.next = cur.next.left
cur = cur.next # cur移动到同层的next
first = first.left # 从本层到下一层，每次从同层第一个节点开始next指针指向
return root
golang
package binaryTree
import "container/list"
type Node struct {
Val int
Left, Right, Next *Node
}
func connect(root *Node) *Node {
res := [][]*Node{}
if root == nil {
return root
}
queue := list.New()
queue.PushBack(root)
var tmpArr []*Node
for queue.Len() > 0 {
length := queue.Len() // 处理本层节点
for i:=0;i<length;i++ {
node := queue.Remove(queue.Front()).(*Node) // 头部节点出队列
if node.Left != nil {
queue.PushBack(node.Left)
}
if node.Right != nil {
queue.PushBack(node.Right)
}
tmpArr = append(tmpArr, node)
}
res = append(res, tmpArr)
tmpArr = []*Node{} // 清空层数据
}
// 上面操作部分与层序遍历一致
// 下面操作，遍历每层元素，指定next
for i:=0;i<len(res);i++ {
for j:=0;j<len(res[i])-1;j++ { // 当层的最后一个不操作，默认指向nil
res[i][j].Next = res[i][j+1]
}
}
return root
}