LeetCode Daily-Question 32

Jul 19th 2022

7 月 19 日 每日一题

117. Populating Next Right Pointers in Each Node II

Given a binary tree

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

1
2
3
Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

思路

The difference between 116 and 117 is that 117 is not a perfect binary tree, which means it cannot be simply solved by recursive.

The direct way is to use iterative BSF. Note that when reach to null, it’s time to move to the next level and add a nullptr to the end of the queue(for the next level end).

There is a O(1) space complexity way, which is a bit similar to double pointer. The detail is in comments of code. Note the when proceed the current level(currParent), the next has been proceed by last while loop.

代码

Way 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
// 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 == nullptr)
            return nullptr;
        queue<Node*>q;
        q.push(root);
        q.push(nullptr);
        while(q.size() > 1){
            Node* curr = q.front();
            q.pop();
            if(!curr){
                q.push(nullptr);
                continue;
            }
            curr->next = q.front();
            if(curr->left)
                q.push(curr->left);
            if(curr->right)
                q.push(curr->right);
        }
        return root;
    }
};

Way 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    Node* connect(Node* root) {
        Node *currParent = root;
        Node *baseChild;
        Node *currChild;
        Node *nextChild;
        while(currParent){
            //reach to a parent with at least one child
            while(currParent->next && !currParent->left && !currParent->right)
                currParent = currParent->next;
            //set baseChild and currChild to the first child of the next level
            currChild = baseChild = currParent->left ? currParent->left : currParent->right;
            while(currChild){
                //if currChild is left child and have right sibling
                if(currParent->right && currParent->right != currChild){
                    nextChild = currParent->right;
                }
                else{
                    //move to the adjacent parent
                    currParent = currParent->next;
                    while(currParent && !currParent->left && !currParent->right){
                        currParent = currParent->next;
                        //now currParent has pointed to the next Parent
                    }
                    //if not reach to the end
                    if(currParent){
                        nextChild = currParent->left ? currParent->left : currParent->right;
                    }
                    //if reach to the end
                    else{
                        //if reach to the end of this level
                        nextChild = nullptr;
                    }
                }
                currChild->next = nextChild;
                currChild = nextChild;
            }
            //move to the next level
            currParent = baseChild;
        }
        return root;
    }
};
, ,
  1. 7 月 19 日 每日一题
    1. 117. Populating Next Right Pointers in Each Node II
    2. 思路
    3. 代码