A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 116. Populating Next Right Pointers in Each Node, the solution in this repository is mainly a two pointers solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- BFS with queue
- time: O(N), space: O(N)
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The solution is organized around the main LeetCode entry point and a few local helpers.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N), space: O(N)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//BFS with queue
02//Runtime: 20 ms, faster than 94.93% of C++ online submissions for Populating Next Right Pointers in Each Node.
03//Memory Usage: 17.5 MB, less than 16.36% of C++ online submissions for Populating Next Right Pointers in Each Node.
04//time: O(N), space: O(N)
05/*
06// Definition for a Node.
07class Node {
08public:
09 int val;
10 Node* left;
11 Node* right;
12 Node* next;
13
14 Node() : val(0), left(NULL), right(NULL), next(NULL) {}
15
16 Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
17
18 Node(int _val, Node* _left, Node* _right, Node* _next)
19 : val(_val), left(_left), right(_right), next(_next) {}
20};
21*/
22
23class Solution {
24public:
25 Node* connect(Node* root) {
26 if(!root) return root;
27
28 queue<Node*> q;
29
30 q.push(root);
31
32 while(!q.empty()){
33 int level_size = q.size();
34
35 Node* prev = nullptr;
36
37 while(level_size-- > 0){
38 Node* cur = q.front(); q.pop();
39
40 if(prev) prev->next = cur;
41
42 if(cur->left) q.push(cur->left);
43 if(cur->right) q.push(cur->right);
44
45 prev = cur;
46 }
47 }
48
49 return root;
50 }
51};
52
53//O(1) space(not consider recursion stack) recursive solution
54//https://leetcode.com/problems/populating-next-right-pointers-in-each-node/discuss/37473/My-recursive-solution(Java)
55//Runtime: 20 ms, faster than 94.93% of C++ online submissions for Populating Next Right Pointers in Each Node.
56//Memory Usage: 17.1 MB, less than 16.36% of C++ online submissions for Populating Next Right Pointers in Each Node.
57class Solution {
58public:
59 Node* connect(Node* root) {
60 if(!root) return root;
61
62 //for each node, process it's left and right children
63 if(root->left){
64 root->left->next = root->right;
65 if(root->next){
66 root->right->next = root->next->left;
67 }
68 }
69
70 //go to next level
71 connect(root->left);
72 connect(root->right);
73
74 return root;
75 }
76};
77
78//O(1) space iterative solution
79//https://leetcode.com/problems/populating-next-right-pointers-in-each-node/discuss/37472/A-simple-accepted-solution
80//Right Pointers in Each Node.
81//Memory Usage: 17 MB, less than 16.36% of C++ online submissions for Populating Next Right Pointers in Each Node.
82//time: O(N), space: O(1)
83class Solution {
84public:
85 Node* connect(Node* root) {
86 if(!root) return root;
87
88 Node *prev = root, *cur = nullptr;
89
90 //while prev is not a leaf
91 while(prev->left){
92 //in each iteration, connect all nodes in prev's next level
93 cur = prev;
94 while(cur){
95 cur->left->next = cur->right;
96 if(cur->next) cur->right->next = cur->next->left;
97 //move rightward, in the same level
98 cur = cur->next;
99 }
100 //go to next level
101 prev = prev->left;
102 }
103
104 return root;
105 }
106};Cost