1. Title Description

Given a perfect binary tree , All its leaf nodes are on the same layer , Each parent node has two children . A binary tree is defined as follows ：

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

Fill in each of its next The pointer , Let this pointer point to its next right node . If the next right node cannot be found , Will next The pointer is set to NULL.

In the initial state , all next The pointer is set to NULL.

Example ：

explain ： A given binary tree is shown in figure A Shown , Your function should fill in every one of its next The pointer , To point to its next right node , Pictured B Shown .

Tips ：
You can only use constant level extra space .
Using recursion to solve problems also meets the requirements , In this problem, the stack space occupied by recursive program is not considered as additional space complexity .

2. Ideas

Because it's a perfect binary tree , Therefore, there is no need to worry about the left subtree and the right subtree , You don't have to worry about a node having a subtree , However, the nodes in the same layer have no subtrees . That is to say, there should be everything , If not, none of them .

2.1 recursive

For recursion , Be sure to establish the relationship between the right and left subtrees of adjacent nodes , otherwise , Of the right subtree of each node next Will be None, That is, if the parent node has Next Node words , Of the right subtree of the parent node next Is the parent node next The left subtree of the node , So that we can make connections .

2.1 python Code

"""
# Definition for a Node.
class Node:
def __init__(self, val, left, right, next):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if root == None:
return None
if root.left == None:
return root
root.left.next = root.right
if root.next: # If root.next exist 
root.right.next = root.next.left
self.connect(root.left)
self.connect(root.right)
return root

2.2 Non recursive

Non recursive words , You can actually go through the queue , To traverse hierarchically , But in that case , Beyond the limits of space complexity .
At each layer of nodes next Nodes are set from the far left , So you need to set a pointer that indicates the leftmost parent node of each layer preNode. Make every cycle from preNode.left At the beginning . For a certain layer , Set from left to right , Each time you need to check whether the parent node has next, If there is one , Create the right child of the parent node and the parent node next The connection between the left subtree of a node .

2.2 python Code

"""
# Definition for a Node.
class Node:
def __init__(self, val, left, right, next):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if root == None:
return None
preNode = root # Record the information of the leftmost node 
curNode = root # Record the information of the parent node of the current child node and update it at any time 
while True:
if curNode.left:
curNode.left.next = curNode.right
if curNode.next: # Check whether the parent node has next, If there's a connection ,
# It also shows that this layer has not been modified , modify curNode For its next node 
curNode.right.next = curNode.next.left
curNode = curNode.next
else: # without next The node , This indicates that this layer has been modified ,
# modify curNode To the left most child node of the next layer , At the same time to modify preNode,
curNode = preNode.left
preNode = curNode
else: # If curNode.left non-existent , It's the last layer , Interruption cycle 
break
return root