# 150. Evaluate Reverse Polish Notation

Difficulty: Medium

Frequency: N/A

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are `+`, `-`, `*`, `/`. Each operand may be an integer or another expression.

Some examples:

```  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6```

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int evalRPN(vector<string>& tokens) {
if (tokens.empty()) return 0;
int n = tokens.size(), result;
stack<int> s;
for (int i = 0; i < n; i++) {
string tmp = tokens[i];
if (tmp == "+" || tmp == "-" || tmp == "*" || tmp == "/") {
int num2 = s.top();
s.pop();
int num1 = s.top();
s.pop();
if (tmp == "+") {
result = num1 + num2;
} else if (tmp == "-") {
result = num1 - num2;
} else if (tmp == "*") {
result = num1 * num2;
} else {
result = num1 / num2;
}
s.push(result);
} else {
s.push(stoi(tmp));
}
}
return s.top();
}
};
```

Solution 2:

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

Submission errors:

Things to learn:

# 084. Largest Rectangle in Histogram

Difficulty: Hard

Frequency: N/A

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height = `[2,1,5,6,2,3]`. The largest rectangle is shown in the shaded area, which has area = `10` unit.

For example,
Given heights = `[2,1,5,6,2,3]`,
return `10`.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size(), area = 0, height, left;
stack<int> idx;
for (int i = 0; i <= n; i++) {
while (i == n || !idx.empty() && heights[idx.top()] > heights[i]) {
if (i == n && idx.empty()) {
height = 0;
i++;
} else {
height = heights[idx.top()];
idx.pop();
}
left = idx.empty() ? -1 : idx.top();
area = max(area, height * (i - left - 1));
}
idx.push(i);
}
return area;
}
};
```

Solution 2:

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

Submission errors:

Things to learn:

# 071. Simplify Path

Difficulty: Medium

Frequency: N/A

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = `"/home/"`, => `"/home"`
path = `"/a/./b/../../c/"`, => `"/c"`

click to show corner cases.

Corner Cases:

• Did you consider the case where path = `"/../"`?
In this case, you should return `"/"`.
• Another corner case is the path might contain multiple slashes `'/'` together, such as `"/home//foo/"`.
In this case, you should ignore redundant slashes and return `"/home/foo"`.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
string simplifyPath(string path) {
vector<string> paths;
string tmp;
stringstream ss(path);
while (getline(ss, tmp, '/')) {
if (tmp == "" || tmp == ".") continue;
if (tmp == ".." && !paths.empty()) paths.pop_back();
else if (tmp != "..") paths.push_back(tmp);
}
string result;
for (string s : paths) result += "/" + s;
return result.empty() ? "/" : result;
}
};
```

Solution 2:

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

Submission errors:

Things to learn:

# 145. Binary Tree Postorder Traversal

Difficulty: Hard

Frequency: N/A

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree `{1,#,2,3}`,

```   1
\
2
/
3
```

return `[3,2,1]`.

Note: Recursive solution is trivial, could you do it iteratively?

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> postorderTraversal(TreeNode* root) {
vector<int> result;
dfs(root, result);
return result;
}
void dfs(TreeNode* node, vector<int>& result) {
if (!node) return;
dfs(node->left, result);
dfs(node->right, result);
result.push_back(node->val);
}
};
```

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

Things to learn:

# 272. (Locked)Closest Binary Search Tree Value II

Difficulty: Hard

Frequency: N/A

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

Note:

• Given target value is a floating point.
• You may assume k is always valid, that is: k ≤ total nodes.
• You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Hint:

1. Consider implement these two helper functions:
1. `getPredecessor(N)`, which returns the next smaller node to N.
2. `getSuccessor(N)`, which returns the next larger node to N.
2. Try to assume that each node has a parent pointer, it makes the problem much easier.
3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
4. You would need two stacks to track the path in finding predecessor and successor node separately.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
vector<int> closestKValues(TreeNode* root, double target, int k) {
priority_queue<pair<double, int>> pq;
vector<int> result;
dfs(root, pq, target, k);
while (!pq.empty()) {
result.push_back(pq.top().second);
pq.pop();
}
return result;
}
void dfs(TreeNode* node, priority_queue<pair<double, int>>& pq, double target, int k) {
if (!node) return;
pq.push(make_pair(abs(target - (double)node->val), node->val));
if (pq.size() > k) pq.pop();
dfs(node->left, pq, target, k);
dfs(node->right, pq, target, k);
}
};
```

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

Things to learn:

# 094. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree `{1,#,2,3}`,

```   1
\
2
/
3
```

return `[1,3,2]`.

Note: Recursive solution is trivial, could you do it iteratively?

Questions:
1. Recursive or iteratively

Test Cases:

1. [#] empty
2.  root only
3. [1, 2, #, 3, #, 4] all left
4. [1, #, 2, #, #, #, 3] all right
5. [1, #, 2, 3] normal

Solution 1:
Data structure:
vector, tree
Method:
Recursive:
1. helper(node->left)
2. push(node->val)
3. helper(node->right)
Complexity:
Runtime:
worst case: o(n^2)
average: o(nlogn)
Space:
o(n)
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> inorderTraversal(TreeNode* root) {
vector<int> result;
inorderTraverse(root, result);
return result;
}
void inorderTraverse(TreeNode *node, vector<int>& result) {
if (!node) return;
inorderTraverse(node->left, result);
result.push_back(node->val);
inorderTraverse(node->right, result);
}
};
```

Solution 2:
Data structure:
Method:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. Tree Traversals:

# 173. Binary Search Tree Iterator

Difficulty: Medium

Frequency: N/A

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling `next()` will return the next smallest number in the BST.

Note: `next()` and `hasNext()` should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
private:
stack<TreeNode*> myStack;
void pushLeft(TreeNode *node) {
for (; node != NULL; node = node->left) myStack.push(node);
}
public:
BSTIterator(TreeNode *root) {
pushLeft(root);
}

/** @return whether we have a next smallest number */
bool hasNext() {
return !myStack.empty();
}

/** @return the next smallest number */
int next() {
TreeNode *tmp = myStack.top();
myStack.pop();
pushLeft(tmp->right);
return tmp->val;
}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
```

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

Things to learn: