Cinte's Leetcode Record
0%

116. Populating Next Right Pointers in Each Node

Posted on Edited on In Disqus:
Symbols count in article: 2.3k Reading time ≈ 2 mins.

116. Populating Next Right Pointers in Each Node

O(n) space
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
45
/*
// 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 nullptr;
        queue<Node*> s;
        s.push(root);
        while(!s.empty())
        {
            int i = s.size();
            while(i-- > 0)
            {
                auto p = s.front();
                s.pop();
                if(i == 0)
                    p->next = nullptr;
                else
                    p->next = s.front();
                if(p->left)
                    s.push(p->left);
                if(p->right)
                    s.push(p->right);
            }
        }
        return root;
    }
};
o(1) space
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
/*
// 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 nullptr;
        Node* father = root;
        Node* cur = nullptr;
        while(father->left)
        {
            cur = father;
            while(cur)
            {
                cur->left->next = cur->right;
                if(cur->next)
                    cur->right->next = cur->next->left;
                cur = cur->next;
            }
            father = father->left;
        }
        return root;
    }
};

每层遍历下去，每层从最左边开始，然后操作他的儿子们，当一层没儿子就停止

递归

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
/*
// 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 nullptr;
        if(root->left)
        {
            root->left->next = root->right;
            root->right->next = root->next ? root->next->left : nullptr;
            connect(root->left);
            connect(root->right);
        }
        return root;
    }
};