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

Title Description

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: the given binary tree is shown in the figure A As shown in, your function should fill each of it next Pointer to point to its next right node, as shown in the figure B As shown in. The serialized output is arranged by sequence traversal, and the nodes of the same layer are composed of next Pointer connection,'#'marks the end of each layer.

Tips:

• The number of nodes in the tree is less than 4096
• − 1000 ≤ n o d e . v a l ≤ 1000 -1000 \le node.val \le 1000 −1000≤node.val≤1000

Solution:

Method 1:

Search widely.

Connect the nodes of the same layer through the next pointer. All nodes of the same layer need to be processed at one time.

Note: it's easier to write from right to left.

Time complexity: O ( n ) O(n) O(n)

Additional space complexity: O ( n ) O(n) O(n)

/*
// 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 root;
        queue<Node*> q;
        q.push( root );
        int i, size;
        Node *pre = NULL, *now = NULL;

        while ( q.size() ) {
            size = q.size();
            pre = NULL;
            for ( int i = 0; i < size; ++i ) {
                now = q.front();
                q.pop();
                now->next = pre;
                pre = now;
                if ( now->right ) q.push( now->right );
                if ( now->left ) q.push( now->left );
            }
        }

        return root;
    }
};
/*
Time: 20ms, defeat: 94.26%
Memory: 16.5MB, beat: 82.31%
*/

Method 2:

The next pointer is not used in method 1. Next, consider using the next pointer.

Consider by layers. Each layer starts from the leftmost node:

• For each node, let the next of the left son point to the right son, and then let the next of the right son point to the left son of the next node. Move to the next node between the same layers through next.
• Until the last floor stops

Each time the current layer is processed, the nodes of the next layer have been connected together through the next pointer, so you can use the next pointer to move between the same layers.

/*
// 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 root;
        Node *now = root, *start = NULL;
        while ( now->left ) {
            start = now;
            while ( start ) {
                start->left->next = start->right;
                if ( start->next )
                    start->right->next = start->next->left;
                start = start->next;
            }
            now = now->left;
        }
        return root;
    }
};
/*
Time: 20ms, defeat: 94.26%
Memory: 16.4MB, beat: 89.45%
*/

Method 3:

Method 2 can also be applied to the implementation of preorder traversal.

Time complexity: O ( n ) O(n) O(n)

Additional space complexity: O ( h ) O(h) O(h) ， h h h is the height of the tree.

/*
// 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 preOrder( Node* root ) {
        if ( !root->left && !root->right ) return;
        root->left->next = root->right;
        if ( root->next )
            root->right->next = root->next->left;
        preOrder( root->left );
        preOrder( root->right );
    }
    Node* connect(Node* root) {
        if ( !root ) return root;
        preOrder( root );
        return root;
    }
};
/*
Time: 20ms, defeat: 94.26%
Memory: 16.4MB, beat: 93.25%
*/