leetcode96--不同的二叉搜索树[java]

leetcode 96 题 不同的二叉搜索树

原题链接:
难度—中等
https://leetcode.cn/problems/unique-binary-search-trees/

题目描述

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例1:

输入：n = 3
输出：5

示例2:
输入：n = 1
输出：1

提示：
1 <= n <= 19

暴力递归

解题思路

第一先明白搜索二叉树得性质:
左 < 头 < 右
因此.在递归时,我们选中一个数字做头节点后,
剩下得数字里,只有小于这个数得才可以做左子树
大于这个数字的,可以做右子树.
最后在计算数量时,
要把可能组建左子树的情况,去乘右子树可能的情况
一个排列组合,应该能想明白把
好了.思路已经很清晰了.
开撸:

代码演示

  public int numTrees(int n) {//	== 1 时 无需处理if(n == 1){return 1;}return process1(1,n);}
/**
* 递归
* L 左边界
* R 右边界
* 左右边界 来确定哪些数字可以用于创建左子树
* 哪些数字可以创建右子树
*/public int process1(int L,int R){//base case 越界了//关于为什么越界要返回1 ,这样理解//L 到 R 一直在考察,怎么创建,如果都考察到越界了,//说明前面的情况成立了,所以返回一个1if(L > R){return 1;}//记录答案int ans = 0;for(int i = L ; i <= R;i++){//左树能组成的不同情况有几种int left = process1(L,i - 1);//右树能组成的不同情况有几种int right = process1(i+1,R);//排列组合的累加就是所有的情况了.ans += left * right;}return ans;}

执行效率

这个暴力的递归,执行起来.在leetcode 上跑不过去,会超出时间限制
但是代码是没问题的,我下面给你验证他是没问题的
代码逻辑不改,我们用递归加缓存 再来一版 ,就能跑过去

递归 + 缓存

解题思路

逻辑和暴力递归是一样的,只是我们加了缓存,
缓存怎么加,就是对递归里的变量进行缓存,
递归中的变量是L 和 R 左右边界,
因此加个二维数组,就可以了,
开撸,上代码

代码演示

  public int numTrees(int n) {if(n == 1){return 1;}//初始值都是0int[][]ans = new int[n + 1][n + 1];return process(1,n,ans);}/*** 递归加缓存* L 左边界* R 右边界* 左右边界 来确定哪些数字可以用于创建左子树* 哪些数字可以创建右子树*/public int process(int L,int R,int[][]nums){if(L > R){return 1;}//不等于0 时 从缓存中拿if(nums[L][R] != 0){return nums[L][R];}//下面逻辑和暴力递归是一样的.int ans = 0;for(int i = L ; i <= R;i++){int left = process(L,i - 1,nums);int right = process(i+1,R,nums);ans += left * right;}//答案保存在缓存中nums[L][R] = ans;return ans;}

执行效率

这个题,可以改动态规划 有兴趣的可以试一下

动态规划专题

斐波那契数列-从暴力递归到动态规划

背包问题–填满背包的最大价格

纸牌博弈问题

零钱兑换,凑零钱问题,从暴力递归到动态规划