-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path117.cpp
More file actions
71 lines (64 loc) · 2.02 KB
/
117.cpp
File metadata and controls
71 lines (64 loc) · 2.02 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// Author: btjanaka (Bryon Tjanaka)
// Problem: (LeetCode) 117
// Title: Populating Next Right Pointers in Each Node II
// Link:
// https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
// Idea: Traverse each layer of the tree using the `next` pointers built by
// traversing the previous layer. As we traverse each layer, we check each
// node's children and build up the next layer.
// Difficulty: medium
// Tags: tree, binary-tree, linked-list
/*
// 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) {
Node *leftmost = root; // Leftmost node on current layer.
Node *next_layer_prev; // Last visited node on the next layer.
Node *cur; // Iterator over the current layer.
// Iterate through each layer. A layer with no nodes will have leftmost =
// NULL.
while (leftmost != NULL) {
next_layer_prev = NULL;
cur = leftmost;
while (cur != NULL) {
// Check each child.
if (cur->left) {
if (next_layer_prev == NULL) {
leftmost = cur->left;
} else {
// Make the child part of the next layer.
next_layer_prev->next = cur->left;
}
// Advance the next layer iterator.
next_layer_prev = cur->left;
}
if (cur->right) {
if (next_layer_prev == NULL) {
leftmost = cur->right;
} else {
next_layer_prev->next = cur->right;
}
next_layer_prev = cur->right;
}
// Advance along this layer.
cur = cur->next;
}
// Next level must be empty.
if (!next_layer_prev) leftmost = NULL;
}
return root;
}
};