1. Title Description

Given a binary tree

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

The only difference between this question and the last one is that the tree is not a perfect binary tree . Therefore, it is necessary that the child nodes may not exist .

2.1 recursive

"""
# 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:
if root.right:
root.left.next = root.right
else:
root.left.next = self.nextNode(root.next)
# If the right subtree doesn't exist , Left subtree next It is the nearest node in the current layer ,
# Therefore, this requires finding the current node's next when , Dexter next The relationship must be complete ,
# otherwise nextNode(root.next) There is clearly , But will return None, There will be errors .
if root.right:
root.right.next = self.nextNode(root.next)
self.connect(root.right)
# Notice that the right subtree must be recursion first , Because if the right subtree of the parent node does not exist ,
# Left subtree next Need to find the parent node next The subtree of ,
# So you have to put the right one first next The relationship is straightened out 
self.connect(root.left)
return root
def nextNode(self,node): # With the aid of an auxiliary function , To find the nearest node 
if node == None:
return None
while node:
if node.left:
return node.left
if node.right:
return node.right
node = node.next
return None

2.2 Non recursive

Hierarchical traversal of the queue is still the simplest way to do it , But space complexity requires .
Queues essentially maintain the order of precedence between nodes , So you can use the... In this topic next Instead of .

2.2 Non recursive 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
firstNode = root
while firstNode:
while firstNode and firstNode.left == None and firstNode.right == None:
firstNode = firstNode.next
# firstNode Is the first node in each layer that has a subtree , and firstNode This layer has been set up next It's all right 
if firstNode == None:
break
cur = firstNode
pre = None #pre = None # Similar to the head node of a linked list 
# pre Used to represent the previous information of the current node , namely pre.next = cur.left(or right)
while cur: # use next Instead of queue, realize the relationship between nodes in current layer .
if cur.left:
if pre:
pre.next = cur.left
pre = cur.left
if cur.right:
if pre:
pre.next = cur.right
pre = cur.right
cur = cur.next
firstNode = firstNode.left if firstNode.left else firstNode.right
return root