描述
Given 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.
Given 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.
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.


Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
We have an array A
of integers, and an array queries
of queries.
For the i
th query val = queries[i][0], index = queries[i][1]
, we add val to A[index]
. Then, the answer to the i
th query is the sum of the even values of A
.
(Here, the given index = queries[i][1] is a 0based index, and each query permanently modifies the array A.)
Return the answer to all queries. Your answer
array should have answer[i]
as the answer to the i
th query.
Example 1:


Note:
1 <= A.length <= 10000
10000 <= A[i] <= 10000
1 <= queries.length <= 10000
10000 <= queries[i][0] <= 10000
0 <= queries[i][1] < A.length
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?