【LetMeFly】116. Fill in the next right node pointer for each node

Force button topic link ：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/

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, 212 - 1]  Within the scope of
• -1000 <= node.val <= 1000

Advanced ：

• 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 .

Method 1 ： Level traversal

In fact, this problem only needs to be binary tree Sequence traversal , Then record the last traversed node while traversing .

If this node is on the same level as the previous node , Then... Of the previous node next Point to this node .

The sequence traversal of binary tree can be referred to LeetCode 102. Sequence traversal of binary tree

• Time complexity $O(N)$, among $N$ Is the number of nodes
• Spatial complexity $O(M)$, among $M$ Is the number of nodes in the last layer

AC Code

C++

typedef pair<Node*, int> pii;
class Solution {
    
public:
    Node* connect(Node* root) {
    
        if (!root)
            return root;
        queue<pii> q;
        q.push({
    root, 1});
        int lastLayer = 0;
        Node* lastNode;
        while (q.size()) {
    
            auto[thisNode, thisLayer] = q.front();
            q.pop();
            if (thisLayer == lastLayer) {
    
                lastNode->next = thisNode;
            }
            lastNode = thisNode;
            lastLayer = thisLayer;
            if (thisNode->left)
                q.push({
    thisNode->left, thisLayer + 1});
            if (thisNode->right)
                q.push({
    thisNode->right, thisLayer + 1});
        }
        return root;
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125821076