Note:

Title:
Given a perfect binary tree, all leaf nodes are in the same layer, and each parent node has two child nodes. Binary tree is defined as follows:

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

Fill in each of its next pointers so that this pointer points to its next right node. If the next right node cannot be found, set the next pointer to NULL.

In the initial state, all next pointers are set to NULL.

Advanced:
You can only use constant level extra space.
Using recursion to solve the problem also meets the requirements. The stack space occupied by the recursive program in this problem is not considered as additional space complexity.

Example:
Input: root = [1,2,3,4,5,6,7]
Output: [1, #, 2,3, #, 4,5,6,7, #]
Explanation: given A binary tree, as shown in figure A, your function should fill in each next pointer to point to its next right node, as shown in Figure B. The serialized output is arranged by sequence traversal, and the nodes of the same layer are connected by the next pointer,'# 'marks the end of each layer.

Tips:
The number of nodes in the tree is less than 4096
-1000 <= node.val <= 1000

Solution:
Idea:

There are two types of next pointers in a tree.

The first case is to connect two children of the same parent node. They can be accessed directly through the same node, so you can complete the connection by performing the following operations.

node.left.next = node.right

The second case is the case of connecting child nodes between different parent nodes. More specifically, the right child of the first parent node and the left child of the second parent node are connected. Since the \ text{next}next pointer has been established at the parent node level, you can directly find the second parent node through the \ text{next}next pointer of the first parent node, and then establish a connection between their children.

node.right.next = node.next.left

Complexity analysis
Time complexity: O(N), each node is accessed only once.
Spatial complexity: O(1), no need to store additional nodes.

Recursive method
Preorder traversal

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    void dfs(Node* root){
        if(root==NULL||root->left==NULL){
            return ;
        }
        root->left->next=root->right;
        root->right->next=(root->next==NULL?NULL:root->next->left);
        dfs(root->left);
        dfs(root->right);
    }
    Node* connect(Node* root) {
        dfs(root);
        return root;
    }
};

Iterative method
level traversal

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        Node* lastfirst=root;
        //Traverse the linked list organized by the nodes of the layer where lastfirst is located, and update the next pointer for the nodes of the next layer
        while(lastfirst!=NULL){
            Node* head=lastfirst;
            while(head!=NULL&&head->left!=NULL){
                head->left->next=head->right;
                head->right->next=(head->next==NULL?NULL:head->next->left);
                head=head->next;
            }
            //Adjust the pointer to the next level
            lastfirst=lastfirst->left;
        }
        return root;
    }
};