提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

计算n个节点的BSF数量，与构造n个节点的BFS的全收集

一、力扣96. 不同的二叉搜索树

class Solution {public int numTrees(int n) {int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i ++){for(int j = 1; j <= i; j ++){dp[i] += dp[j-1] * dp[i-j];}}return dp[n];}
}

回溯

class Solution {int[][] memo;public int numTrees(int n) {memo = new int[n+1][n+1];return fun(1,n);}public int fun(int low, int high){if(low > high){return 1;}if(memo[low][high] != 0){return memo[low][high];}int res = 0;for(int i = low; i <= high; i ++){res += fun(low, i-1) * fun(i+1,high);}memo[low][high] = res;return res;}
}

二、力扣95. 不同的二叉搜索树 II

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<TreeNode> generateTrees(int n) {List<TreeNode> res = new LinkedList<>();if(n == 0){return res;}return fun(1,n);}public List<TreeNode> fun(int low, int high){List<TreeNode> res = new LinkedList<>();if(low > high){res.add(null);return res;}for(int i = low; i <= high; i ++){List<TreeNode> l = fun(low,i-1);List<TreeNode> r = fun(i+1,high);for(TreeNode tl : l){for(TreeNode tr : r){TreeNode cur = new TreeNode(i);cur.left = tl;cur.right = tr;res.add(cur);}}}return res;}
}