左神算法之二叉树的个数

1. 题目

给定节点个数，问，能返回多少个不同的二叉树

2. 解释

略

3. 思路

使用递归，当 n 是1 的时候，值是1， 当 n 是 2 的时候，值是 2
节点个数是左侧节点的变化 * 右侧节点的变化

4. 代码

public class Proble06_UniqueBST {public static int numTrees(int n) {int[] dp = new int[n + 1];dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j < i; j++) {dp[i] += dp[j] * dp[i - j - 1];}}return dp[n];}// 递归public static int process(int n) {if (n < 2) {return 1;}int ans = 0;for (int i = 0; i <= n - 1; i++) {int left = process(i);int right = process(n - 1 - i);ans += left * right;}return ans;}public static void main(String[] args) {int n = 5;System.out.println(numTrees(n));System.out.println(process(n));}
}

5. 总结

一个递归就好解决了吗，so easy