# LeetCode Contains Duplicate II

219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true


Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true


Example 3:

Input: nums = [1,2,3,1,2,3], k = 2 Output: false

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
if (nums.size() == 0)
return false;
unordered_map<int, int> hash_table;
int distinct_cnt = 1; // 相异元素的个数
vector<vector<int> > duplicate_indices = { {} }; // 跳过第0个桶
for (int i = 0; i < nums.size(); i++) {
if (hash_table[nums[i]] == 0) {
hash_table[nums[i]] = distinct_cnt++;
duplicate_indices.push_back({ i });
}
else {
duplicate_indices[hash_table[nums[i]]].push_back(i);
// 把相同元素的下标都放到一个桶里
}
}
for (int i = 1; i < duplicate_indices.size(); i++) {
// 查每个桶
if (duplicate_indices[i].size() < 2)
continue;
for (int u = 0; u < duplicate_indices[i].size() – 1; u++) {
for (int v = u + 1; v < duplicate_indices[i].size(); v++) {
if (duplicate_indices[i][v] – duplicate_indices[i][u] <= k)
return true;
}
}
}
return false;
}
};

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
if (nums.size() == 0 || k <= 0)
return false;
if (k >= nums.size())
k = nums.size() – 1;
unordered_set<int> hash_set;
for (int i = 0; i < nums.size(); i++) {
if (i > k)
hash_set.erase(nums[i – k – 1]); // 滑动窗口，删掉窗口第一个元素
if (hash_set.find(nums[i]) != hash_set.end())
return true;
hash_set.insert(nums[i]); // 把新元素插入窗口
}
return false;
}
};

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_map<int, int> hash;
for (int i = 0; i < nums.size(); ++i) {
if (hash.find(nums[i]) != hash.end() && i – hash[nums[i]] <= k)
return true;
hash[nums[i]] = i;
}
return false;
}
};

# LeetCode Contains Duplicate

217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2] Output: true

class Solution {
public:
bool containsDuplicate(vector<int>& nums)
{
unordered_map<int, int> hash_table;
for (int i = 0; i < nums.size(); i++) {
hash_table[nums[i]]++; // 如果元素不存在hash_table中，会自动插入，并赋值为0，++之后为1
if (hash_table[nums[i]] > 1)
return true;
}
return false;
}
};

# LeetCode Sum Root to Leaf Numbers

129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]
1
/ \
2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
4
/ \
9   0
/ \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

class Solution {
public:
void dfs(int& sum, int sub_sum, TreeNode* root)
{
if (root->left == NULL && root->right == NULL) {
sum += (sub_sum * 10 + root->val);
return;
}
if (root->left != NULL)
dfs(sum, sub_sum * 10 + root->val, root->left);
if (root->right != NULL)
dfs(sum, sub_sum * 10 + root->val, root->right);
}
int sumNumbers(TreeNode* root)
{
if (root == NULL)
return 0;
int sum = 0;
dfs(sum, 0, root);
return sum;
}
};

# LeetCode Binary Tree Level Order Traversal

102. Binary Tree Level Order Traversal

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],

    3
/ \
9  20
/  \
15   7


return its level order traversal as:

[
[3],
[9,20],
[15,7]
]

class Solution {
public: void bfs(vector < vector < int >> & ans, TreeNode * root) {
queue < TreeNode * > tree;
tree.push(root);
TreeNode * front;
while (!tree.empty()) {
vector < int > cand;
bool pushed = false;
TreeNode * next_level = NULL; // 下一层的第一个节点
front = tree.front();
while (!tree.empty() && front != next_level) {
tree.pop();
cand.push_back(front - > val);
if (front - > left != NULL) {
tree.push(front - > left);
if (!pushed) {
next_level = front - > left; // 标记
pushed = true; // 标记
}
}
if (front - > right != NULL) {
tree.push(front - > right);
if (!pushed) {
next_level = front - > right; // 标记
pushed = true; // 标记

}
}
if (tree.empty()) break;
front = tree.front();
}
ans.push_back(cand);
}
}
vector < vector < int >> levelOrder(TreeNode * root) {
vector < vector < int >> ans;
if (root == NULL) return ans;
bfs(ans, root);
return ans;
}
};

class Solution {
public: vector < vector < int >> levelOrder(TreeNode * root) {
vector < vector < int >> ans;
if (root == NULL) return ans;
queue < TreeNode * > tree;
tree.push(root);
TreeNode * f;
while (!tree.empty()) {
int n = tree.size();
vector < int > one_level;
for (int i = 0; i < n; i++) {
f = tree.front();
tree.pop();
one_level.push_back(f - > val);
if (f - > left != NULL) tree.push(f - > left);
if (f - > right != NULL) tree.push(f - > right);
}
ans.push_back(one_level);
}
return ans;
}
};

 class Solution {
public: void work(vector < vector < int >> & ans, int level, TreeNode * root) {
if (ans.size() == level) ans.push_back({}); // 重点
ans[level].push_back(root - > val);
if (root - > left != NULL) work(ans, level + 1, root - > left); // 先左
if (root - > right != NULL) work(ans, level + 1, root - > right); // 后右
}
vector < vector < int >> levelOrder(TreeNode * root) {
vector < vector < int >> ans;
if (root == NULL) return ans;
work(ans, 0, root);
return ans;
}
};

# LeetCode Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5


class Solution {
public:
{
ListNode *prior = new_head, *tail = prior->next;
while (tail != NULL) {
if (tail->val == val) {
prior->next = prior->next->next;
tail = prior->next;
}
else {
prior = prior->next;
tail = prior->next;
}
}
}
};

class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *dummy = new ListNode(0);
ListNode *tail = dummy;
tail = tail->next;
}
}
tail->next = NULL;
return dummy->next;
}
};

# LeetCode Path Sum II

113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
/ \
4   8
/   / \
11  13  4
/  \    / \
7    2  5   1


Return:

[
[5,4,11,2],
[5,8,4,5]
]

class Solution {
public:
void dfs(vector<vector<int> >& ans, vector<int>& path, int& target, int cur, TreeNode* root)
{
if (root->left == NULL && root->right == NULL) {
if (cur + root->val == target) {
path.push_back(root->val);
ans.push_back(path);
path.pop_back();
}
return;
}
if (root->left != NULL) {
path.push_back(root->val);
dfs(ans, path, target, cur + root->val, root->left);
path.pop_back();
}
if (root->right != NULL) {
path.push_back(root->val);
dfs(ans, path, target, cur + root->val, root->right);
path.pop_back();
}
}
vector<vector<int> > pathSum(TreeNode* root, int sum)
{
vector<vector<int> > ans;
if (root == NULL)
return ans;
vector<int> path;
dfs(ans, path, sum, 0, root);
return ans;
}
};

class Solution {
private:
void dfs(vector<vector<int> >& ans, vector<int>& candidate, TreeNode* root, int sum)
{
candidate.push_back(root->val);
sum -= root->val;
if (root->left == NULL && root->right == NULL && sum == 0) {
ans.push_back(candidate);
}
if (root->left != NULL)
dfs(ans, candidate, root->left, sum);
if (root->right != NULL)
dfs(ans, candidate, root->right, sum);
candidate.pop_back();
}
public:
vector<vector<int> > pathSum(TreeNode* root, int sum)
{
if (root == NULL)
return {};
vector<vector<int> > ans;
vector<int> candidate;
dfs(ans, candidate, root, sum);
return ans;
}
};

class Solution {
public:
void dfs(TreeNode *root, vector<vector<int>> &ans, vector<int> &cand, int sum) {
if (root->left == NULL && root->right == NULL && sum == 0) {
ans.push_back(cand);
return;
}
if (root->left != NULL) {
cand.push_back(root->left->val);
sum -= root->left->val;
dfs(root->left, ans, cand, sum);
sum += root->left->val;
cand.pop_back();
}
if (root->right != NULL) {
cand.push_back(root->right->val);
sum -= root->right->val;
dfs(root->right, ans, cand, sum);
sum += root->right->val;
cand.pop_back();
}
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if (root == NULL)return {};
vector<vector<int>> ans;
vector<int> cand = { root->val };
dfs(root, ans, cand, sum - root->val);
return ans;
}
};

# LeetCode Path Sum

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
/ \
4   8
/   / \
11  13  4
/  \      \
7    2      1


return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

class Solution {
public:
void dfs(set<int>& vals, int cur, TreeNode* root)
{
if (root->left == NULL && root->right == NULL) {
vals.insert(cur + root->val);
return;
}
if (root->left != NULL) {
dfs(vals, cur + root->val, root->left);
}
if (root->right != NULL) {
dfs(vals, cur + root->val, root->right);
}
}
bool hasPathSum(TreeNode* root, int sum)
{
if (root == NULL)
return false;
set<int> vals;
dfs(vals, 0, root);
if (vals.count(sum) > 0)
return true;
else
return false;
}
};

class Solution {
public:
bool hasPathSum(TreeNode* root, int sum)
{
if (root == NULL)
return false;
if (root->left == NULL && root->right == NULL && root->val == sum)
return true;
if (root->left == NULL && root->right == NULL && root->val != sum)
return false;
if (root->left != NULL)
if (hasPathSum(root->left, sum – root->val))
return true;
if (root->right != NULL)
if (hasPathSum(root->right, sum – root->val))
return true;
return false;
}
};

# LeetCode Binary Tree Postorder Traversal

145. Binary Tree Postorder Traversal

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

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [3,2,1]


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

class Solution {
public:
void work(vector<int>& ans, TreeNode* root)
{
if (root == NULL)
return;
work(ans, root->left);
work(ans, root->right);
ans.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root)
{
vector<int> ans;
work(ans, root);
return ans;
}
};

class Solution {
public:
vector<int> postorderTraversal(TreeNode* root)
{
vector<int> ans;
if (root == NULL)
return ans;
stack<TreeNode*> tree;
TreeNode *curr, *pre = NULL;
tree.push(root); // 根
while (!tree.empty()) {
curr = tree.top();
if ((curr->left == NULL && curr->right == NULL) || // 已到叶子节点
(pre != NULL && (curr->left == pre || curr->right == pre))) { // 回溯的时候
ans.push_back(curr->val);
tree.pop();
pre = curr;
}
else {
if (curr->right != NULL)
tree.push(curr->right); // 右
if (curr->left != NULL)
tree.push(curr->left); // 左
}
}
return ans;
}
};

 class Solution {
public: vector < int > postorderTraversal(TreeNode * root) {
vector < int > ans;
if (root == NULL) return ans;
stack < TreeNode * > s1, s2;
TreeNode * top;
s1.push(root); // 根
while (!s1.empty()) {
top = s1.top(); // (1)
s1.pop(); // (1)
s2.push(top); // (1)
if (top - > left != NULL) {
// 左
s1.push(top - > left);
}
if (top - > right != NULL) {
// 右
s1.push(top - > right);
}
}
while (!s2.empty()) {
top = s2.top();
ans.push_back(top - > val);
s2.pop();
}
return ans;
}
};

class Solution {
public:
void PutAllLeft(TreeNode *root, stack<TreeNode*> &stk) {
while (root != NULL) {
stk.push(root);
root = root->left;
}
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> stk;
PutAllLeft(root, stk);
TreeNode *pre = NULL;
while (!stk.empty()) {
TreeNode *cur = stk.top();
if (cur->right != NULL && cur->right != pre) {
PutAllLeft(cur->right, stk);
}
else {
ans.push_back(cur->val);
stk.pop();
pre = cur;
}
}
return ans;
}
};

# LeetCode Binary Tree Preorder Traversal

144. Binary Tree Preorder Traversal

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

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,2,3]


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

class Solution {
public:
void work(vector<int>& ans, TreeNode* root)
{
if (root == NULL)
return;
ans.push_back(root->val);
work(ans, root->left);
work(ans, root->right);
}
vector<int> preorderTraversal(TreeNode* root)
{
vector<int> ans;
work(ans, root);
return ans;
}
};

class Solution {
public:
vector<int> preorderTraversal(TreeNode* root)
{
vector<int> ans;
if (root == NULL)
return ans;
stack<TreeNode*> tree;
tree.push(root);
TreeNode* top;
while (!tree.empty()) {
top = tree.top();
ans.push_back(top->val);
tree.pop();
if (top->right != NULL) { // 先压栈右子树
tree.push(top->right);
}
if (top->left != NULL) { // 再压栈左子树
tree.push(top->left);
}
}
return ans;
}
};

# LeetCode Binary Tree Inorder Traversal

94. Binary Tree Inorder Traversal

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

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]

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

class Solution {
public:
void work(vector<int>& ans, TreeNode* root)
{
if (root == NULL)
return;
work(ans, root->left); // 左
ans.push_back(root->val); // 根
work(ans, root->right); // 右
}
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> ans;
work(ans, root);
return ans;
}
};

class Solution {
public:
void putAllLeft(TreeNode* root, stack<TreeNode*>& tree)
{
while (root != NULL) {
tree.push(root);
root = root->left;
}
}
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> ans;
stack<TreeNode*> tree;
putAllLeft(root, tree); // 找最左边的叶子节点
TreeNode* top;
while (!tree.empty()) {
top = tree.top();
ans.push_back(top->val); // 访问左（根）节点
tree.pop();
putAllLeft(top->right, tree); // 访问右节点
}
return ans;
}
};