98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:

　The left subtree of a node contains only nodes with keys less than the node’s key.
　The right subtree of a node contains only nodes with keys greater than the node’s key.
　Both the left and right subtrees must also be binary search trees.

Example 1:
　　　2
　　 /　 \
　　1　 3
Binary tree [2,1,3], return true.

Example 2:
　　　1
　　 / 　\
　 2 3
Binary tree [1,2,3], return false.

97. Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = “aabcc”,
s2 = “dbbca”,

When s3 = “aadbbcbcac”, return true.
When s3 = “aadbbbaccc”, return false.

96. Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

95. Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

94. Binary Tree Inorder Traversal

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

For example :
Given binary tree[1, null, 2, 3],
　　1
　　　\
　　　2
　　　/
　　3
return[1, 3, 2]

93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

92. Reverse Linked List II

Reverse a linked list from position m to n.Do it in - place and in one - pass.

For example :
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.

Note :
Given m, n satisfy the following condition :
1 ≤ m ≤ n ≤ length of list.

90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:
[
　　[2],
　　[1],
　　[1,2,2],
　　[2,2],
　　[1,2],
　　[]
]

89. Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.