问题描述:
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
原问题链接:https://leetcode.com/problems/unique-binary-search-trees/
问题分析
这个问题的难点在于要找到一个递归的关系来描述它。对于给定n个节点的二叉搜索树来说,它到底有多少种构成情况呢?我们先从一些最初始的情况来看。
当只有0个和1个节点的情况下,肯定构成的二叉搜索树数量是1。当有2个节点的时候呢?它主要的构成如下图:
如果对上述的问题更加一般化,对于一个长度为i的串来说,当要求它所有可能构成的二叉搜索树的话,它可能的构成是有这个串里每个节点都是根节点的所有情况。先假定里面取节点j的情况来看,它将是一个如下图的情况:
在上图中,我们可以看到在以节点j作为根节点的情况下,它的左子树对应着前面这个问题里f(0, i) 的子问题f(0, j - 1),它的右子树对应着这个问题里的子问题f(j + 1, i)。那么对于以j为根节点的情况它所有可能的子树的数量则是两个子树的可能数量的乘积,也就是说f(0, i) = f(0, j - 1) * f(j + 1, i)。
这里仅仅是对应一个节点为根的情况。在实际的情况中,我们是每个节点都可能为根节点,所以应该是它们每个节点为根的情况的数量的求和。
用递归的方式表达的话就是f(n) = sum(f(i) * f(n - i - 1)) (i = 1, ... n)。 同时我们也有了初始条件f(0) = f(1) = 1。
在具体的实现里,我们可以考虑用到动态规划的思路,我们创建一个长度为n + 1的数组int[] nums = new int[n + 1]; 最开始的nums[0] = 1表示没有元素的时候,可以构造的二叉搜索树的数量是1,同样nums[1] = 1,剩下的就是基于这个去递推的计算。
按照上述的思路,可以得到详细的实现代码如下:
public class Solution { public int numTrees(int n) { if(n <= 1) return 1; int[] nums = new int[n + 1]; nums[0] = nums[1] = 1; for(int i = 2; i <= n; i++) { for(int j = 0; j < i; j++) nums[i] += nums[j] * nums[i - j - 1]; } return nums[n]; } }
相关推荐
leetcode的题目:Balanced Binary Tree
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
最终450 Love Babbar 450问题
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
leetcode:leetcode刷题
leetcode卡 leetcode 自己刷leetcode,然后记录下来。。。相当于打卡吧! (Unique Binary Search Trees需要用)
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
LeetCode:LeetCode的代码
Leetcode:LeetCode解题代码
LeetCode:LeetCode的注释