LeetCode 116. Populate the next right node pointer for each node

116. Fill in the next right node pointer for each node

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 1：

 Input ：root = [1,2,3,4,5,6,7]
 Output ：[1,#,2,3,#,4,5,6,7,#]
 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 . The output of the serialization is arranged in sequence traversal , Nodes on the same layer are controlled by  next  Pointer connection ,'#'  It marks the end of every layer .

Example 2:

 Input ：root = []
 Output ：[]

Tips ：

• The number of nodes in the tree is [0, 2^12 - 1] Within the scope of
• -1000 <= node.val <= 1000

2） analysis

recursive .

First, consider that the root node is empty , Returns a null pointer directly .

When the root node is not empty , Consider that the root node has a leaf node . So the left leaf node next Point to the right leaf node .

Consider that the current root node has a parent node , Then the current root node must have a sibling node （ reference FigureB Medium 2）, Then the right leaf node of the current root node （ reference FigureB Medium 5） Of next It should point to the current root node next The point of reference （ reference FigureB Medium 3） Left leaf node of （ reference FigureB Medium 6）.

3）C++ Code

/* // 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) {
    
        if(!root)
            return NULL;
        if(root->left){
    
            root->left->next=root->right;
            if(root->next)
                root->right->next=root->next->left;
        }

        connect(root->left);
        connect(root->right);
        return root;
    }
};