Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
class Solution {
public:
bool isBalanced(TreeNode* root) {
if (!root) return true;
int left = depth(root->left);
int right = depth(root->right);
return abs(left-right)<=1 && isBalanced(root->left) && isBalanced(root->right);
}
int depth(TreeNode* root) {
if (!root) return 0;
return 1+max(depth(root->left), depth(root->right));
}
};
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
class Solution {
public:
int minDepth(TreeNode* root) {
if (!root) return 0;
if (!root->left && !root->right) return 1;
if (!root->left) return 1+minDepth(root->right);
if (!root->right) return 1+minDepth(root->left);
return 1+min(minDepth(root->left), minDepth(root->right));
}
};
Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums, 0, nums.size()-1);
}
TreeNode* helper(vector<int> &nums, int i, int j) {
if (i>j) return NULL;
int mid = i+(j-i)/2;
TreeNode* node = new TreeNode(nums[mid]);
node->left = helper(nums, i, mid-1);
node->right = helper(nums, mid+1, j);
return node;
}
};
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if (!head) return NULL;
if (!head->next) return new TreeNode(head->val);
ListNode* slow = head;
ListNode* fast = head;
ListNode* tail = NULL;
while (fast && fast->next) {
tail = slow;
slow = slow->next;
fast = fast->next->next;
}
tail->next = NULL;
TreeNode* node = new TreeNode(slow->val);
node->left = sortedListToBST(head);
node->right = sortedListToBST(slow->next);
return node;
}
};
Binary Tree Traversal (Preorder, Inorder, Level order)
Given a binary tree, return the preorder traversal of its nodes’ values.
For example: Given binary tree {1,#,2,3}, return [1,2,3].
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
helper(root, res);
return res;
}
void helper(TreeNode* root, vector<int> &res) {
if (!root) return;
res.push_back(root->val);
helper(root->left, res);
helper(root->right, res);
}
};
Given a binary tree, return the inorder traversal of its nodes’ values.
For example: Given binary tree [1,null,2,3], return [1,3,2].
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
helper(root, res);
return res;
}
void helper(TreeNode* root, vector<int> &res) {
if (!root) return;
helper(root->left, res);
res.push_back(root->val);
helper(root->right, res);
}
};
Given a binary tree, return the postorder traversal of its nodes’ values.
For example: Given binary tree {1,#,2,3}, return [3,2,1];
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
helper(root, res);
return res;
}
void helper(TreeNode* root, vector<int> &res) {
if (!root) return;
helper(root->left, res);
helper(root->right, res);
res.push_back(root->val);
}
};
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,null,null,15,7], return
[
[3],
[9,20],
[15,7]
]
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
helper(root, res, 0);
return res;
}
void helper(TreeNode* root, vector<vector<int>> &res, int depth) {
if (!root) return;
if (res.size() <depth+1)
res.push_back(vector<int>());
res[depth].push_back(root->val);
helper(root->left, res, depth+1);
helper(root->right, res, depth+1);
}
};
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,null,null,15,7], return
[
[15,7],
[9,20],
[3]
]
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
helper(root, res, 0);
reverse(res.begin(), res.end());
return res;
}
void helper(TreeNode* root, vector<vector<int>> &res, int depth) {
if (!root) return;
if (res.size() <depth+1)
res.push_back(vector<int>());
res[depth].push_back(root->val);
helper(root->left, res, depth+1);
helper(root->right, res, depth+1);
}
};
Linked List Series
Given a linked list, remove the nth node from the end of list and return its head.
For example, Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note: Given n will always be valid. Try to do this in one pass.
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* prev = new ListNode(0);
prev->next = head;
ListNode* prehead = prev;
while (n--) head = head->next;
ListNode* curr = head;
while (head) {
prehead=prehead->next;
head=head->next;
}
prehead->next = prehead->next->next;
return prev->next;
}
};
Given a list, rotate the list to the right by k places, where k is non-negative.
For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (!head || !head->next) return head;
ListNode* curr = head;
int len = 0;
while (curr) {
curr = curr->next;
len++;
}
k %= len;
if (k==0) return head;
curr = head;
ListNode* prev = head;
while (curr->next) {
curr = curr->next;
if (k)
k--;
else
prev=prev->next;
}
curr->next = head;
head = prev->next;
prev->next = NULL;
return head;
}
};
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions.
For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.
class Solution {
public:
ListNode* partition(ListNode* root, int x) {
if (!root || !root->next) return root;
ListNode* l1 = new ListNode(0);
ListNode* p1 = l1;
ListNode* l2 = new ListNode(0);
ListNode* p2 = l2;
while (root) {
if (root->val < x) {
p1->next = root;
p1 = p1->next;
}
else {
p2->next = root;
p2 = p2->next;
}
root = root->next;
}
p2->next = NULL;
p1->next = l2->next;
return l1->next;
}
};
Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (!head) return head;
head->next = removeElements(head->next, val);
return head->val==val?head->next:head;
}
};
Dynamic Programming
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
dp[1][0] = 1;
for (int i=1; i<m+1; i++)
for (int j=1; j<n+1; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
return dp[m][n];
}
};
Follow up for “Unique Paths”: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example, There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid.empty()) return 0;
if (obstacleGrid[0][0] == 1) return 0;
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (i==0 && j==0) obstacleGrid[i][j] = 1;
else if (obstacleGrid[i][j]==0) {
obstacleGrid[i][j] = (i>=1? obstacleGrid[i-1][j]:0) + (j>=1 ? obstacleGrid[i][j-1]:0);
}
else
obstacleGrid[i][j] = 0;
}
}
return obstacleGrid[m-1][n-1];
}
};
Leetcode 33. Search in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()) return -1;
int left=0, right = nums.size();
while (left < right) {
int mid = left+(right-left)/2;
if (nums[mid]==target) return mid;
if (nums[mid] > nums[left]) {
if (nums[left]<=target && target<nums[mid])
right = mid;
else
left = mid+1;
}
else {
if (nums[mid]<target && target<=nums[right-1])
left = mid+1;
else
right = mid;
}
}
return -1;
}
};
Follow up for “Search in Rotated Sorted Array”: What if duplicates are allowed?
Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array.
class Solution {
public:
bool search(vector<int>& nums, int target) {
if (nums.empty()) return false;
int left=0, right = nums.size();
while (left < right) {
int mid = left+(right-left)/2;
if (nums[mid]==target) return true;
if (nums[mid] > nums[left]) {
if (nums[left]<=target && target<nums[mid])
right = mid;
else
left = mid+1;
}
else if (nums[mid] < nums[left]) {
if (nums[mid]<target && target<=nums[right-1])
left = mid+1;
else
right = mid;
}
else
left++;
}
return false;
}
};
```