# 286. (Locked)Walls and Gates

Difficulty: Medium

Frequency: N/A

You are given a m x n 2D grid initialized with these three possible values.

1. `-1` – A wall or an obstacle.
2. `0` – A gate.
3. `INF` – Infinity means an empty room. We use the value `231 - 1 = 2147483647` to represent `INF` as you may assume that the distance to a gate is less than`2147483647`.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with `INF`.

For example, given the 2D grid:

```INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
0  -1 INF INF```

After running your function, the 2D grid should be:

```  3  -1   0   1
2   2   1  -1
1  -1   2  -1
0  -1   3   4```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
private:
struct Grid {
int p, q, d;
Grid(int p_, int q_, int d_) : p(p_), q(q_), d(d_) {}
};
public:
void wallsAndGates(vector<vector<int>>& rooms) {
if (rooms.empty()) return;
int m = rooms.size(), n = rooms.size();
queue<Grid> myQ;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!rooms[i][j]) {
myQ.push(Grid(i - 1, j, 1));
myQ.push(Grid(i + 1, j, 1));
myQ.push(Grid(i, j - 1, 1));
myQ.push(Grid(i, j + 1, 1));
while (!myQ.empty()) {
Grid cur = myQ.front();
myQ.pop();
if (cur.p < 0 || cur.p >= m || cur.q < 0 || cur.q > n || rooms[cur.p][cur.q] < d) continue;
rooms[cur.p][cur.q] = d;
myQ.push(Grid(cur.p - 1, cur.q, d + 1));
myQ.push(Grid(cur.p + 1, cur.q, d + 1));
myQ.push(Grid(cur.p, cur.q - 1, d + 1));
myQ.push(Grid(cur.p, cur.q + 1, d + 1));
}
}
}
}
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 130. Surrounded Regions

Difficulty: Medium

Frequency: N/A

Given a 2D board containing `'X'` and `'O'`, capture all regions surrounded by `'X'`.

A region is captured by flipping all `'O'`s into `'X'`s in that surrounded region.

For example,

```X X X X
X O O X
X X O X
X O X X
```

After running your function, the board should be:

```X X X X
X X X X
X X X X
X O X X
```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
void solve(vector<vector<char>>& board) {
int width = board.size();
if (!width) return;
int length = board.size();
if (!length) return;
for (int i = 0; i < width; i++) {
if (board[i] == 'O') flip(board, i, 0);
if (board[i][length - 1] == 'O') flip(board, i, length - 1);
}
for (int j = 1; j < length - 1; j++) {
if (board[j] == 'O') flip(board, 0, j);
if (board[width - 1][j] == 'O') flip(board, width - 1, j);
}
for (int i = 0; i < width; i++) {
for (int j = 0; j < length; j++) {
if (board[i][j] == 'T') board[i][j] = 'O';
else if (board[i][j] == 'O') board[i][j] = 'X';
}
}
}
void flip(vector<vector<char>>& board, int i, int j) {
int width = board.size();
int length = board.size();
queue<pair<int, int>> myQ;
myQ.push(make_pair(i, j));
board[i][j] = 'T';
while (!myQ.empty()) {
pair<int, int> cur = myQ.front();
myQ.pop();
int p = cur.first, q = cur.second;
if (p > 0 && board[p - 1][q] == 'O') {
myQ.push(make_pair(p - 1, q));
board[p - 1][q] = 'T';
}
if (p < width - 1 && board[p + 1][q] == 'O') {
myQ.push(make_pair(p + 1, q));
board[p + 1][q] = 'T';
}
if (q > 0 && board[p][q - 1] == 'O') {
myQ.push(make_pair(p, q - 1));
board[p][q - 1] = 'T';
}
if (q < length - 1 && board[p][q + 1] == 'O') {
myQ.push(make_pair(p, q + 1));
board[p][q + 1] = 'T';
}
}
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 199. Binary Tree Right Side View

Difficulty: Medium

Frequency: N/A

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

```   1            <---
/   \
2     3         <---
\     \
5     4       <---
```

You should return `[1, 3, 4]`.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> results;
if (!root) return results;
queue<TreeNode*> myQ;
myQ.push(root);
while (!myQ.empty()) {
int q_size = myQ.size();
while (q_size) {
TreeNode *cur = myQ.front();
if (q_size == 1) results.push_back(cur->val);
myQ.pop();
if (cur->left) myQ.push(cur->left);
if (cur->right) myQ.push(cur->right);
q_size--;
}
}
return results;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 107. Binary Tree Level Order Traversal II

Difficulty: Easy

Frequency: N/A

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree `{3,9,20,#,#,15,7}`,

```    3
/ \
9  20
/  \
15   7
```

return its bottom-up level order traversal as:

```[
[15,7],
[9,20],

]```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> results;
if (!root) return results;
queue<TreeNode*> myQ;
myQ.push(root);
while (!myQ.empty()) {
int q_size = myQ.size();
vector<int> tmp;
while (q_size) {
TreeNode *cur = myQ.front();
tmp.push_back(cur->val);
myQ.pop();
if (cur->left) myQ.push(cur->left);
if (cur->right) myQ.push(cur->right);
q_size--;
}
results.push_back(tmp);
}
return vector<vector<int>> (results.rbegin(), results.rend());
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 102. Binary Tree Level Order Traversal

Difficulty: Easy

Frequency: N/A

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree `{3,9,20,#,#,15,7}`,

```    3
/ \
9  20
/  \
15   7
```

return its level order traversal as:

```[
,
[9,20],
[15,7]
]```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> results;
if (!root) return results;
queue<TreeNode*> myQ;
myQ.push(root);
while (!myQ.empty()) {
vector<int> tmp;
int q_size = myQ.size();
while (q_size) {
TreeNode *cur = myQ.front();
tmp.push_back(cur->val);
myQ.pop();
if (cur->left) myQ.push(cur->left);
if (cur->right) myQ.push(cur->right);
q_size--;
}
results.push_back(tmp);
}
return results;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: