# LeetCode 116: 填充每个节点的下一个右侧节点指针 Populating Next Right Pointers in Each Node

### 题目:

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

```struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
```

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to `NULL`.

Initially, all next pointers are set to `NULL`.

img

```输入：root = [1,2,3,4,5,6,7]

```

• 你只能使用常量级额外空间。
• 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

• You may only use constant extra space.
• Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

• 树中的节点数小于 `4096`
• `-1000 <= node.val <= 1000` Constraints:
• The number of nodes in the given tree is less than `4096`.
• `-1000 &lt;= node.val &lt;= 1000`

### 解题思路:

• 一个结点的左孩子的 `next` 指针指向该结点的右孩子
• 一个结点的右孩子的 `next` 指针指向该结点的 `next` 结点的左孩子

```node.left.next=node.right;
node.right.next=node.next.left;
```

### Java：

```class Solution {
public Node connect(Node root) {
if(root == null)
return root;
// 记录每层的最左结点，该层遍历结束后利用最左侧结点进入下一层
Node most_left = root;
Node node = root;
while(most_left.left!=null){// 最左侧结点的下一层只要存在结点，则继续操作
if(node.left != null)
node.left.next=node.right;
if(node.next != null){ // 判断该结点是否为该层的最后一个结点
node.right.next = node.next.left;
node = node.next; // 刷新该结点为 next 结点
}else{
most_left = most_left.left; // 刷新最左侧结点
node = most_left;
}
}
return root;
}
}
```

### Python：

```class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
# 记录每层的最左结点，该层遍历结束后利用最左侧结点进入下一层
most_left = root
node = root
while most_left.left: # 最左侧结点的下一层只要存在结点，则继续操作
if node.left:
node.left.next = node.right
if node.next: # 判断该结点是否为该层的最后一个结点
node.right.next = node.next.left
node = node.next # 刷新该结点为 next 结点
else:
node = most_left.left # 刷新最左侧结点
most_left = node
return root
```

0 条评论

• ### LeetCode 116. 填充每个节点的下一个右侧节点指针（递归&循环）

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

• ### Leetcode No.116 填充每个节点的下一个右侧节点指针（BFS）

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

• ### ​LeetCode刷题实战116：填充每个节点的下一个右侧节点指针

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就...

• ### 【Leetcode】117. 填充每个节点的下一个右侧节点指针 II

struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 nex...

• ### LeetCode117：填充每个节点的下一个右侧节点指针 II

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

• ### LeetCode 117. 填充每个节点的下一个右侧节点指针 II（递归&循环）

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

• ### ​LeetCode刷题实战117：填充每个节点的下一个右侧节点指针 II

https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/

• ### 2021-10-08：填充每个节点的下一个右侧节点指针。给定一个

2021-10-08：填充每个节点的下一个右侧节点指针。给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个 next 指针...

• ### 【一天一大 lee】填充每个节点的下一个右侧节点指针 (难度:中等) - Day20201015

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

• ### 【一天一大 lee】填充每个节点的下一个右侧节点指针 II (难度:中等) - Day20200928

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

• ### LeetCode题解—填充二叉树节点右侧指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

• ### 2021-10-08：填充每个节点的下一个右侧节点指针。给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节

2021-10-08：填充每个节点的下一个右侧节点指针。给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个 next 指针...

• ### 【Leetcode】116. 填充同一层的兄弟节点

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

• ### 打卡群刷题总结0814——二叉树展开为链表

链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node

• ### LeetCode1-120题汇总，希望对你有点帮助！

时间很快，公众号发布的LeetCode题目，已经达到120道题了。今天把发布的1-120篇LeetCode文章整理一下，平时文章都放在比较末尾，阅读量都不高，相...

• ### 【LeetCode两题选手】算法类题目（8.7）

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

• ### LeetCode-算法-广度和深度优先搜索-第8天

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他...

• ### 剑指 Offer 52. 两个链表的第一个公共节点(指针法)

思路：用两个指针分别指向A,B的头结点，然后循环遍历链表，当A遍历完后将其指向B的头结点，B遍历完后将其指向A的头结点。