-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path116.cpp
More file actions
56 lines (50 loc) · 1.56 KB
/
116.cpp
File metadata and controls
56 lines (50 loc) · 1.56 KB
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
// Author: btjanaka (Bryon Tjanaka)
// Problem: (LeetCode) 116
// Title: Populating Next Right Pointers in Each Node
// Link:
// https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
// Idea: Do a BFS on the tree, while keeping track of the level of each node.
// By adding left and then right children, you are able to traverse the tree
// from left to right, so after popping each node, make it point to the next
// node on the queue (assuming they are at the same level).
// Difficulty: medium
// Tags: binary-tree, bfs
/*
// 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) {
queue<pair<Node*, int>> q;
if (root != NULL) q.push({root, 0});
while (!q.empty()) {
Node* cur;
int lvl;
tie(cur, lvl) = q.front();
q.pop();
if (q.empty() || q.front().second != lvl) {
// If the level is not the same.
cur->next = NULL;
} else {
// If the level is the same, point to the node on the front of the
// queue.
cur->next = q.front().first;
}
// Add left and then right child.
if (cur->left) q.push({cur->left, lvl + 1});
if (cur->right) q.push({cur->right, lvl + 1});
}
return root;
}
};