[路飞]_leetcode-96-不同的二叉搜索树

简介: leetcode-96-不同的二叉搜索树

网络异常,图片无法展示
|


[题目地址][B站地址]


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


示例 1:


网络异常,图片无法展示
|


输入: n = 3
输出: 5
复制代码


示例 2:


输入: n = 1
输出: 1
复制代码


提示:


  • 1 <= n <= 19


解题思路


本题可以想到的一个最直接的思路就是根据给定的 n 获取 1~nn 个节点,然后根据 n 个节点构建二叉搜索树,返回可以构建的数量即可。


但是本题其实不需要返回构建的树,只需要返回构建的树的种数,所以如果按以上思路解题,虽然可以得到结果,但是效率会很低,也没有必要。那如何才能在不构建树的情况下还能得到树的数量呢?


其实 n 个节点组成的二叉搜索树的种数,可以拆解为以 1 为根,2 为根 … n 为根的二叉搜索树的种数之和。同时每个值为根的二叉搜索树的数量等于可能的左子树的数量 * 可能的右子树的数量。


接下来我们看一下 n 不同的时候,每个值为根的左右子树节点的数量关系。


网络异常,图片无法展示
|


我们可以根据左右子树节点数量及之前推导出的 n 对应的树的种数推导后面的 n 对应的树的种数。


所以本题不需要真的进行树的构建,只需要根据以 1~n 的每一个值为根,求得左子树的可能数量,右子树的可能数量,进行相乘,就得到了以当前值为根的数量,1~n 的数量相加,就是 n 个节点组成二叉搜索树的数量。


动画演示


网络异常,图片无法展示
|


代码实现


var numTrees = function(n) {
  // 初始化 整数=>种数数组
  const arr = Array(n+1).fill(0);
  arr[0] = 1,arr[1] = 1;
  // 通过现有结果推导后续结果
  for(let i = 2;i<=n;i++){
    // 获取 1~i 每一个值为根组成二叉搜索树的数量
    for(let j = 1;j<=i;j++){
      arr[i] += arr[j-1]*arr[i-j]
    }
  }
  return arr[n]
};
复制代码


对称优化


根据上面的图我们可以看到,当 n = 4 的时候,以 1 为根和以 4 为根的左右子树的数量是对称的,又因为当前值为根的二叉搜索树的数量等于可能的左子树的数量 * 可能的右子树的数量,所以其实 以 1 为根和以 4 为根的二叉搜索树的数量是相等的。


根据这样的一个性质,我们在求解 n 对应的二叉搜索树的数量的时候,只需要求得前半部分的数量然后 *2 即可。这里要注意的是 n 为奇数的情况,需要单独处理一下中间值为根的二叉搜索树的数量。


代码实现


// 根据对称性质优化
var numTrees = function(n) {
  // 初始化 整数=>种数数组
  const arr = Array(n+1).fill(0);
  arr[0] = 1,arr[1] = 1;
  // 通过现有结果推导后续结果
  for(let i = 2;i<=n;i++){
    const mid = i>>1;
    // 获取 1~mid 每一个值为根组成二叉搜索树的数量
    for(let j = 1;j<=i;j++){
      arr[i] += arr[j-1]*arr[i-j]
    }
    // 数量 *2 获取对称后半部分的数量
    arr[i] *= 2;
    // 如果 i 为奇数,获取中间值为根的二叉搜索树的数量
    if(i%2) arr[i] += arr[mid]*arr[i-mid-1]
  }
  // 返回 n 对应二叉搜索树种数
  return arr[n]
};
复制代码


至此我们就完成了 leetcode-96-不同的二叉搜索树


如有任何问题或建议,欢迎留言讨论!

相关文章
|
2月前
【LeetCode 45】701.二叉搜索树中的插入操作
【LeetCode 45】701.二叉搜索树中的插入操作
13 1
|
2月前
【LeetCode 44】235.二叉搜索树的最近公共祖先
【LeetCode 44】235.二叉搜索树的最近公共祖先
20 1
|
2月前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
43 0
|
2月前
【LeetCode 47】669.修剪二叉搜索树
【LeetCode 47】669.修剪二叉搜索树
12 0
|
2月前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
21 0
|
2月前
【LeetCode 42】501.二叉搜索树中的众数
【LeetCode 42】501.二叉搜索树中的众数
10 0
|
2月前
【LeetCode 41】530.二叉搜索树的最小绝对差
【LeetCode 41】530.二叉搜索树的最小绝对差
14 0
|
2月前
【LeetCode 40】98.验证二叉搜索树
【LeetCode 40】98.验证二叉搜索树
16 0
|
2月前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
18 0
|
4月前
|
算法
LeetCode第96题不同的二叉搜索树
文章介绍了LeetCode第96题"不同的二叉搜索树"的解法,利用动态规划的思想和递推公式,通过计算以任意节点为根的不同二叉搜索树的数量,解决了该问题。
LeetCode第96题不同的二叉搜索树