当前位置:首页 » 《随便一记》 » 正文

LeetCode 96. 不同的二叉搜索树

28 人参与  2023年01月20日 15:25  分类 : 《随便一记》  评论

点击全文阅读


????

欢迎来到茶色岛独家岛屿,本期将为大家揭晓LeetCode 96. 不同的二叉搜索树,做好准备了么,那么开始吧。

????

一、题目名称

二、题目要求

三、相应举例

四、限制要求

五、解决办法

六、代码实现

方法一:动态规划

方法二:递归


一、题目名称

LeetCode 96. 不同的二叉搜索树

二、题目要求

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

三、相应举例

示例 1:

输入:n = 3输出:5

示例 2:

输入:n = 1输出:1

四、限制要求

1 <= n <= 8

五、解决办法

动态规划

题目要求是计算不同二叉搜索树的个数。为此,我们可以定义两个函数:

G(n): 长度为 n 的序列能构成的不同二叉搜索树的个数。

F(i, n): 以 i为根、序列长度为 n 的不同二叉搜索树个数 (1≤i≤n)。

可见,G(n) 是我们求解需要的函数。

稍后我们将看到,G(n) 可以从 F(i,n) 得到,而F(i,n) 又会递归地依赖于 G(n)。

对于边界情况,当序列长度为 1(只有根)或为 0(空树)时,只有一种情况,即:
G(0)=1,G(1)=1

六、代码实现

方法一:动态规划

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

 外层for循环是遍历G中从2开始到n的每个节点,目的是为了求出类似于G(2),G(3)等等,若直接使用下面的循环,如下图:

刚开始会出现G(2)=0,求出G(n)=0的现象,而

使用外层循环可以依次求出G(2),G(3)等,即节点的二叉搜索树的种数,可以防止这种情况出现。如下图:

 每次循环可依次求出G(2),G(3)等二叉搜索树的种数,直到最后求G(n)。

方法二:递归

        Map<Integer, Integer> map = new HashMap<>();    public int numTrees(int n) {                if (n == 0 || n == 1){            return 1;        }        //防止重复递归查找        if (map.containsKey(n)){            return map.get(n);        }        int count = 0;        //当i为根节点时        for (int i = 1; i <= n; i++) {                      count+=numTrees(i-1)*numTrees(n-i);        }        map.put(n,count);        return count;    }

 

 

 


点击全文阅读


本文链接:http://zhangshiyu.com/post/51673.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 给你的第三封信是遗言在线全书顾温言沈佳芮在线
  • 当女配看见弹幕后,被病娇男主强制爱了续集(裴纪洲江柠)_当女配看见弹幕后,被病娇男主强制爱了续集(裴纪洲江柠)
  • 「都市:比悍匪还猛,你管这叫警察?」章节限时抢先看‌_[苏浩]精彩章节免费试读
  • [乖乖女甜又野,偏执贺总失控沦陷]全集阅读_「温黎贺行舟」完结版免费阅读
  • 当女配看见弹幕后,被病娇男主强制爱了+结局+番外(裴纪洲江柠)列表_当女配看见弹幕后,被病娇男主强制爱了+结局+番外
  • 沈青禾霍沉洲+后续+结局(沈青禾霍沉洲)列表_沈青禾霍沉洲+后续+结局(沈青禾霍沉洲)全书+后续+结局在线
  • 全文当女配看见弹幕后,被病娇男主强制爱了+结局+番外(裴纪洲江柠)列表_全文当女配看见弹幕后,被病娇男主强制爱了+结局+番外
  • 当女配看见弹幕后,被病娇男主强制爱了结局+番外免费_(裴纪洲江柠)当女配看见弹幕后,被病娇男主强制爱了结局+番外列表_笔趣阁(裴纪洲江柠)
  • 当女配看见弹幕后,被病娇男主强制爱了+后续+结局(裴纪洲江柠)_(当女配看见弹幕后,被病娇男主强制爱了+后续+结局)列表_笔趣阁(裴纪洲江柠)
  • 陆斐年沈卿卿(偏我情深一往结局+番外)完结_(陆斐年沈卿卿)列表_笔趣阁(偏我情深一往结局+番外)
  • 全文桃花依然笑春风(陆乘渊云梵音)列表_全文桃花依然笑春风
  • 半是风雨半是霜全书+后续+结局(顾宴辞宋相欢)免费_(半是风雨半是霜全书+后续+结局)顾宴辞宋相欢列表_笔趣阁(顾宴辞宋相欢)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1