Given a set of candidate numbers © and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Example

For example, given candidate set 2,3,6,7 and target 7, A solution set is: [7] [2, 2, 3]

Note

All numbers (including target) will be positive integers. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).

The solution set must not contain duplicate combinations.

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example

For example, If n = 4 and k = 2, a solution is: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.

Example

Given binary search tree:

1
2
3
4
5

    5
   / \
  3   6
 / \
2   4

Remove 3, you can either return:

1
2
3
4
5

    5
   / \
  2   6
   \
4

or

1
2
3
4
5

    5
   / \
  4   6
 /
2

Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tree.

Example

Given binary search tree as follow, after Insert node 6, the tree should be:

1
2
3
4
5

  2             2
 / \           / \
1   4   -->   1   4
   /             / \ 
  3             3   6

Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘deserialization’.

There is no limit of how you deserialize or serialize a binary tree, you only need to make sure you can serialize a binary tree to a string and deserialize this string to the original structure.

Example

An example of testdata: Binary tree {3,9,20,#,#,15,7}, denote the following structure:

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

Our data serialization use bfs traversal. This is just for when you got wrong answer and want to debug the input.

You can use other method to do serializaiton and deserialization.

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

Example

Given:

1
2
3
4
5

    1
   / \
  2   3
 / \
4   5

return [1,2,4,5,3].

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.

Example

If k1 = 10 and k2 = 22, then your function should return [12, 20, 22].

1
2
3
4
5

    20
   /  \
  8   22
 / \
4   12

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

Example

Given binary tree {3,9,20,#,#,15,7},

1
2
3
4
5

    3
   / \
  9  20
    /  \
  15   7

return its level order traversal as:

1
2
3
4
5

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

Challenge

Challenge 1: Using only 1 queue to implement it.

Challenge 2: Use DFS algorithm to do it.

Given preorder and inorder traversal of a tree, construct the binary tree.

Example

Given in-order [1,2,3] and pre-order [2,1,3], return a tree:

1
2
3

  2
 / \
1   3

Note

You may assume that duplicates do not exist in the tree.

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example

Given a binary tree as follow:

1
2
3
4
5

  1
 / \ 
2   3
   / \
  4   5

The maximum depth is 3.