题目地址(96. 不同的二叉搜索树)

https://leetcode-cn.com/problems/unique-binary-search-trees/

题目描述

  1. 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
  5. 示例 1：
  7. 输入：n = 3
  8. 输出：5
  11. 示例 2：
  13. 输入：n = 1
  14. 输出：1
  19. 提示：
  21. 1 <= n <= 19

前置知识


公司

  • 暂无

思路

首先确定dp数组的含义
dp[i]为 1- i 为节点 组成的二叉搜索树的个数
当i为1时 dp[i]就是只有一个
image.png
当i= 2时dp[i]的二叉搜索树有两个
image.png
当i= 3时dp[i]的二叉搜索树有五个
image.png
当节点为1的时候 下面的情况和 dp[2]的时候一样 也就是节点为1时 右子树为dp[2]左子树为dp[0]什么也没有 但是dp[0]不能为0 不然后面相乘就为0了 就让他为1
当节点为2的时候 左子树和右子树的情况和dp[1]一样 也就是左右子树都是dp[1]
当节点为3的时候 和节点1相同 只是换成了左子树
每个节点的二叉搜索树的个数为左子树的dp[i]乘上右子树的dp[i] 因为这是排列组合的原理
image.png
所以这样就可以找到一个规律
当节点为1时 dp[3] += dp[0] dp[2]
当节点为2时 dp[3] += dp[1] dp[1]
当节点为3时 dp[3] += dp[2] * dp[0]
image.png

  1. 确定dp数组的含义
    dp[i]为 1- i 为节点 组成的二叉搜索树的个数
  2. 确定递推公式
    假设n= 3
    i为外层循环 求dp[3]需要从dp[2]..之前的状态推导
    j为内层循环 为1-3中每一个j的组成的二叉搜索树的个数
    dp[i] += dp[j-1] * dp[i-j]
    j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量
    这里可以画个图理解一下
  3. dp数组初始化
    dp[0]为1 上面说过了后面的都可以用这个来推导
  4. 循环的顺序
    首先一定是遍历节点数，从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。
    那么遍历i里面每一个数作为头结点的状态，用j来遍历
  5. 举例推导dp数组
    其实这一步我都是在确定递归公式之前做的

    关键点


代码

  • 语言支持：Java

Java Code:

  1. class Solution {
  2.         public int numTrees(int n) {
  3.             int[] dp = new int[n + 1];
  4.             dp[0] = 1;
  5.             for (int i = 1; i <= n; i++) {
  6.                 for (int j = 1; j <=i ; j++) {
  7.                     dp[i] += dp[j-1] * dp[i-j];
  8.                 }
  9.             }
  10.             return dp[n];
  11.         }
  12.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：96. 不同的二叉搜索树 - 图6
  • 空间复杂度：96. 不同的二叉搜索树 - 图7#card=math&code=O%28n%29&id=IAhZ8)