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

@TOC

## # 题目描述

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

``````输入：{"\$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}

``````

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

## # 解题方法

### # 递归

``````"""
# Definition for a Node.
class Node(object):
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
"""

class Solution(object):
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
if not root: return
if root.right:
root.left.next = root.right
if root.next:
root.right.next = root.next.left
self.connect(root.left)
self.connect(root.right)
return root
``````

## # 日期

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