统计和生成所有不同的二叉树
给定一个整数N,中序遍历结果为{1,2,3…N}，返回可能的二叉树结构有多少
方法
num[a]表示a个节点的搜索二叉树有多少种可能，如果以i作为头结点，i的左子树有i-1个节点，有num[i-1]种，右子树有N-i个节点，所以有num(N-i)种，所以以i为头节点的可能性为num(i-1)*num(N-i)
public int numTrees(int n){
if(n < 2){
return 1;
}
//第n个有多少种
int[] num = new int[n+1];
num[0] = 1;
for(int i = 1; i < n + 1; i++){
for(int j = 1; j < i + 1; j++){
num[i] += num[j-1]*num[i-j];
}
}
return num[n];
}
给定一个整数N,中序遍历结果为{1,2,3…N}，返回可能的二叉树
方法
对于以i节点为头结点的节点，用{a…i-1}递归生成左子树的所有结构，所有结构的头节点保存在left.{i+1…end}递归生成右子树的所有结构，所有结构的头结点保存在right. left的每一种结构都可以与right结构一起构成单独的结构。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<TreeNode> generateTrees(int n) {
if(n == 0){
return new LinkedList<TreeNode>();
}
return generate(1,n);
}
public List<TreeNode> generate(int start, int end){
List<TreeNode> res = new LinkedList<TreeNode>();
if(start > end){
res.add(null);
return res;
}
for(int i = start; i <= end; i++){
List<TreeNode> left = generate(start, i-1);
List<TreeNode> right = generate(i+1, end);
for(TreeNode tLeft : left){
for(TreeNode tRight : right){
TreeNode root = new TreeNode(i);
root.left = tLeft;
root.right = tRight;
res.add(root);
}
}
}
return res;
}
}