Unique Binary Search Trees
Give the number of nodes , return the number of different binary search trees possible. As in binary search tree, values of in-order traversal are aways increasing. So the tree labeling is unique once the structure of binary search tree is given.
We can use a dynamic programing algorithm to solve this problem. Let denotes count of binary search trees that have nodes, then we have:
public class UniqueBinarySearchTrees {
public int numTrees(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j < i; j++) {
dp[i] += dp[j] * dp[i - j - 1];
}
}
return dp[n];
}
}
If all possible trees is asked to be returned. We use recursively ways to solve the problems.
We right a general function to generate all possible binary search trees of every elements in
range l
and r
inclusively and trigger the function with l = 1
and r = n
.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class UniqueBinarySearchTreesII {
public List<TreeNode> generateTrees(int l, int r) {
ArrayList<TreeNode> res = new ArrayList<TreeNode>();
if (l > r) {
res.add(null);
return res;
}
for (int i = l; i <= r; i++) {
List<TreeNode> leftTrees = generateTrees(l, i - 1);
List<TreeNode> rightTrees = generateTrees(i + 1, r);
for (TreeNode left : leftTrees) {
for (TreeNode right : rightTrees) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
res.add(root);
}
}
}
return res;
}
public List<TreeNode> generateTrees(int n) {
return generateTrees(1, n);
}
}