-
Notifications
You must be signed in to change notification settings - Fork 118
/
116. Populating Next Right Pointers in Each Node.cpp
106 lines (85 loc) · 3.08 KB
/
116. Populating Next Right Pointers in Each Node.cpp
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
//BFS with queue
//Runtime: 20 ms, faster than 94.93% of C++ online submissions for Populating Next Right Pointers in Each Node.
//Memory Usage: 17.5 MB, less than 16.36% of C++ online submissions for Populating Next Right Pointers in Each Node.
//time: O(N), space: 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);
while(!q.empty()){
int level_size = q.size();
Node* prev = nullptr;
while(level_size-- > 0){
Node* cur = q.front(); q.pop();
if(prev) prev->next = cur;
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
prev = cur;
}
}
return root;
}
};
//O(1) space(not consider recursion stack) recursive solution
//https://leetcode.com/problems/populating-next-right-pointers-in-each-node/discuss/37473/My-recursive-solution(Java)
//Runtime: 20 ms, faster than 94.93% of C++ online submissions for Populating Next Right Pointers in Each Node.
//Memory Usage: 17.1 MB, less than 16.36% of C++ online submissions for Populating Next Right Pointers in Each Node.
class Solution {
public:
Node* connect(Node* root) {
if(!root) return root;
//for each node, process it's left and right children
if(root->left){
root->left->next = root->right;
if(root->next){
root->right->next = root->next->left;
}
}
//go to next level
connect(root->left);
connect(root->right);
return root;
}
};
//O(1) space iterative solution
//https://leetcode.com/problems/populating-next-right-pointers-in-each-node/discuss/37472/A-simple-accepted-solution
//Right Pointers in Each Node.
//Memory Usage: 17 MB, less than 16.36% of C++ online submissions for Populating Next Right Pointers in Each Node.
//time: O(N), space: O(1)
class Solution {
public:
Node* connect(Node* root) {
if(!root) return root;
Node *prev = root, *cur = nullptr;
//while prev is not a leaf
while(prev->left){
//in each iteration, connect all nodes in prev's next level
cur = prev;
while(cur){
cur->left->next = cur->right;
if(cur->next) cur->right->next = cur->next->left;
//move rightward, in the same level
cur = cur->next;
}
//go to next level
prev = prev->left;
}
return root;
}
};