144. Binary Tree Preorder Traversal

Difficulty: Medium

Frequency: N/A

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

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

1
\
2
/
3

return [1,2,3].

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

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:

224. Basic Calculator

Difficulty: Medium

Frequency: N/A

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
int calculate(string s) {
int result = 0, num = 0, sign = 1;
stack<int> tmp;
for (char c : s) {
if (isdigit(c)) {
num = num * 10 + (c - '0');
} else if (c == '+') {
result = result + sign * num;
num = 0;
sign = 1;
} else if (c == '-') {
result = result + sign * num;
num = 0;
sign = -1;
} else if (c == '(') {
tmp.push(result);
tmp.push(sign);
result = 0;
sign = 1;
} else if (c == ')') {
result = result + sign * num;
result = result * tmp.top();
tmp.pop();
result = result + tmp.top();
tmp.pop();
num = 0;
}
}
result += num * sign;
return result;
}
};

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

Things to learn:

255. (Locked)Verify Preorder Sequence in Binary Search Tree

Difficulty: Medium

Frequency: N/A

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Could you do it using only constant space complexity?

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
int low = INT_MIN;
stack<int> path;
for (int p : preorder) {
if (p < low) return false;
while (!path.empty() && p > path.top()) low = path.pop();
path.push(p);
}
return true;
}
}

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

Things to learn:

232. Implement Queue using Stacks

Difficulty: Easy

Frequency: N/A

Implement the following operations of a queue using stacks.

• push(x) — Push element x to the back of queue.
• pop() — Removes the element from in front of queue.
• peek() — Get the front element.
• empty() — Return whether the queue is empty.

Notes:

• You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Queue {
public:
// Push element x to the back of queue.
void push(int x) {
stack<int> tmp;
while (!s.empty()) {
tmp.push(s.top());
s.pop();
}
s.push(x);
while (!tmp.empty()) {
s.push(tmp.top());
tmp.pop();
}
}

// Removes the element from in front of queue.
void pop(void) {
s.pop();
}

// Get the front element.
int peek(void) {
return s.top();
}

// Return whether the queue is empty.
bool empty(void) {
return s.empty();
}
private:
stack<int> s;
};

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

Things to learn:

155. Min Stack

Difficulty: Easy

Frequency: N/A

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• getMin() — Retrieve the minimum element in the stack.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class MinStack {
public:
void push(int x) {
if (trackMin.empty() || x <= getMin()) trackMin.push(x);
s.push(x);
}

void pop() {
if (trackMin.top() == s.top()) trackMin.pop();
s.pop();
}

int top() {
return s.top();
}

int getMin() {
return trackMin.top();
}
private:
stack<int> s, trackMin;
};

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

Things to learn:

225. Implement Stack using Queues

Difficulty: Easy

Frequency: N/A

Implement the following operations of a stack using queues.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• empty() — Return whether the stack is empty.

Notes:

• You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Stack {
public:
// Push element x onto stack.
void push(int x) {
queue<int> tmp;
while (!q.empty()) {
tmp.push(q.front());
q.pop();
}
q.push(x);
while(!tmp.empty()) {
q.push(tmp.front());
tmp.pop();
}
}

// Removes the element on top of the stack.
void pop() {
q.pop();
}

// Get the top element.
int top() {
return q.front();
}

// Return whether the stack is empty.
bool empty() {
return q.empty();
}
private:
queue<int> q;
};

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

Things to learn: