96.不同的二叉搜索树
96.不同的二叉搜索树
题解
题目：给一个中序数组1~n，求能构造出多少种不同的二叉搜索数
递归
1.不同的二叉搜索树，根节点不同 2.根节点相同的树，子树根节点不同 3.当前节点子树个数=左子树个数*右子树个数
动态规划
dp[n]:n个节点存在二叉排序树的个数 f[i]:以i为根的二叉排序树的个数 dp[n]=f[1]+f[2]+...+f[n] 当i为根时，其左子树个数i-1,右子树个数n-i f[i]=dp[i-1]*dp[n-i] 卡特兰数公式:dp[n]=dp[0]*dp[n-1]+dp[1]*dp[n-2]+...+dp[n-1]*dp[0]
代码
func numTrees(n int) int { mp := make(map[int]int) var dfs func(int) int dfs = func(n int) int { if n == 0 || n == 1 { return 1 } if v, ok := mp[n]; ok { return v } cnt := 0 for i := 1; i <= n; i++ { //用i作为根节点 //左边多少子树 leftNum := dfs(i - 1) //右边多少子树 rightNum := dfs(n - i) //相乘就是当前节点子树个数 cnt += leftNum * rightNum } mp[n] = cnt return cnt } return dfs(n) }
func numTrees(n int) int { //dp[n]:n个节点存在二叉排序树的个数 //f[i]:以i为根的二叉排序树的个数 //dp[n]=f[1]+f[2]+...+f[n] //当i为根时，其左子树个数i-1,右子树个数n-i //f[i]=dp[i-1]*dp[n-i] //dp[n]=dp[0]*dp[n-1]+dp[1]*dp[n-2]+...+dp[n-1]*dp[0] dp := make([]int, n+1) dp[0] = 1 dp[1] = 1 for i := 2; i <= n; i++ { //dp[n],这里i=公式里的n f := 0 for j := 1; j <= i; j++ { //f[1~n] f = dp[j-1] * dp[i-j] dp[i] += f //dp[n]=f[1]+f[2]+...+f[n] } } return dp[n] }
