# 226. Invert Binary Tree

Difficulty: Easy

Frequency: N/A

Invert a binary tree.

```     4
/   \
2     7
/ \   / \
1   3 6   9```

to

```     4
/   \
7     2
/ \   / \
9   6 3   1```

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:
TreeNode* invertTree(TreeNode* root) {
invert(root);
return root;
}
void invert(TreeNode *node) {
if (!node) return;
TreeNode *tmp = node->left;
node->left = node->right;
node->right = tmp;
invert(node->left);
invert(node->right);
}
};
```

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

Things to learn:

# 235. Lowest Common Ancestor of a Binary Search Tree

Difficulty: Easy

Frequency: N/A

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

```        _______6______
/              \
___2__          ___8__
/      \        /      \
0      _4       7       9
/  \
3   5
```

For example, the lowest common ancestor (LCA) of nodes `2` and `8` is `6`. Another example is LCA of nodes `2` and `4` is `2`, since a node can be a descendant of itself according to the LCA definition.

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:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || !p || !q) return NULL;
if (p->val == q->val) return p;
int large = max(p->val, q->val), small = min(p->val, q->val);
while (root) {
if (root->val > large) {
root = root->left;
} else if (root->val < small) {
root = root->right;
} else return root;
}
}
};
```

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

Things to learn:

# 270. (Locked)Closest Binary Search Tree Value

Difficulty: Easy

Frequency: N/A

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

• Given target value is a floating point.
• You are guaranteed to have only one unique value in the BST that is closest to the target.

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:
int closestValue(TreeNode* root, double target) {
if (!root) return 0;
int closest = root->val;
while (root) {
if (abs(closest - target) >= abs(root->val - target))
closest = root->val;
root = target > closest ? root->right : root->left;
}
return closest;
}
};
```

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

Things to learn:

# 201. Bitwise AND of Numbers Range

Difficulty: Medium

Frequency: N/A

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int shift = 0;
while (m != n) {
shift++;
m = m >> 1;
n = n >> 1;
}
return m << shift;
}
};
```

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

Things to learn:

# 103. Binary Tree Zigzag Level Order Traversal

Difficulty: Medium

Frequency: N/A

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

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

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

return its zigzag level order traversal as:

```[
,
[20,9],
[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>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> results;
if (!root) return results;
deque<TreeNode*> deq;
deq.push_front(root);
bool front = true;
while (!deq.empty()) {
int s_size = deq.size();
vector<int> result;
while (s_size) {
if (front) {
TreeNode *cur = deq.front();
deq.pop_front();
result.push_back(cur->val);
if (cur->left) deq.push_back(cur->left);
if (cur->right) deq.push_back(cur->right);
} else {
TreeNode *cur = deq.back();
deq.pop_back();
result.push_back(cur->val);
if (cur->right) deq.push_front(cur->right);
if (cur->left) deq.push_front(cur->left);
}
s_size--;
}
front = !front;
results.push_back(result);
}
return results;
}
};
```

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

Things to learn:

# 317. (Locked)Shortest Distance from All Buildings

Difficulty: Hard

Frequency: N/A

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You are given a 2D grid of values 0, 1 or 2, where:

Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.
The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x – p1.x| + |p2.y – p1.y|.

For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

1 – 0 – 2 – 0 – 1
|    |     |     |    |
0 – 0 – 0 – 0 – 0
|     |     |     |    |
0 – 0 – 1 – 0 – 0
The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
if (grid.empty()) return 0;
int m = grid.size(), n = grid.size();
int nb = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) nb++;
}
}
int result = INT_MAX;
bool found = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) continue;
int dist = 0, cnt = 0;
vector<int> start = {i, j, 0};
queue<vector<int>> myQ;
myQ.push(start);
vector<vector<bool>> visited = (m, vector<int>(n, false));
visited[i][j] = true;
while (!myQ.empty()) {
int p = myQ.front();
int q = myQ.front();
int steps = myQ.front();
myQ.pop();
if (grid[p][q] == 1) {
cnt++;
dist += steps;
}
if (grid[p][q] == 0 || (p == i) && (q == j)) {
if (p - 1 >= 0 && grid[p - 1][q] > 2 && !visisted[p - 1][q]) {
vector<int> tmp = {p - 1, q, steps + 1};
myQ.push(tmp);
visited[p - 1][q] = true;
}
if (p + 1 < m && grid[p + 1][q] > 2 && !visisted[p + 1][q]) {
vector<int> tmp = {p + 1, q, steps + 1};
myQ.push(tmp);
visited[p + 1][q] = true;
}
if (q - 1 >= 0 && grid[p][q - 1] > 2 && !visisted[p][q - 1]) {
vector<int> tmp = {p, q - 1, steps + 1};
myQ.push(tmp);
visited[p][q - 1] = true;
}
if (q + 1 < n && grid[p][q + 1] > 2 && !visisted[p][q + 1]) {
vector<int> tmp = {p, q + 1, steps + 1};
myQ.push(tmp);
visited[p][q + 1] = true;
}
}
}
if (grid[i][j] == 1 && cnt < nb) return -1;
if (grid[i][j] == 0 && cnt == nb) {
found = true;
result = min(disk, result);
}
}
}
return found ? result : -1;
}
}
```

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

Things to learn:

# 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: