What is the pattern used to solve Unique Binary Search Trees?

The problem is solved using dynamic programming, where each subproblem represents the number of BSTs that can be formed with a subset of nodes. The result is built iteratively based on smaller subtrees.

How can we optimize the solution for large n in Unique Binary Search Trees?

To optimize, we can use memoization to store the results of previously computed subproblems, preventing redundant calculations. Additionally, the Catalan number formula can be used for direct computation in some cases.

What is the time complexity of the dynamic programming approach?

The time complexity of the dynamic programming approach is O(n^2) due to the nested loops required to compute the number of BSTs for each node. Space complexity is O(n).

How does the recursive formula for Unique Binary Search Trees work?

The recursive formula for the number of unique BSTs is G(n) = sum(G(i) * G(n-i-1)) for i in [0, n-1], where each node is considered as the root, and its left and right subtrees are computed independently.

Can the number of unique BSTs be computed using Catalan numbers?

Yes, the number of unique BSTs corresponds to the nth Catalan number, which can be computed directly using the formula C(n) = (2n)! / ((n+1)! * n!).

#96

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

不同的二叉搜索树

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

数学动态规划树二叉搜索树二叉树

题目描述

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

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示 $[1, i]$ 能产生的二叉搜索树的个数，初始时 $f[0] = 1$ ，答案为 $f[n]$ 。

我们可以枚举节点数 $i$ ，那么左子树节点数 $j \in [0, i - 1]$ ，右子树节点数 $k = i - j - 1$ ，左子树节点数和右子树节点数的组合数为 $f[j] \times f[k]$ ，因此 $f[i] = \sum_{j = 0}^{i - 1} f[j] \times f[i - j - 1]$ 。

最后返回 $f[n]$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为节点数。

1

2

3

4

5

6

7

8

class Solution:
    def numTrees(self, n: int) -> int:
        f = [1] + [0] * n
        for i in range(n + 1):
            for j in range(i):
                f[i] += f[j] * f[i - j - 1]
        return f[n]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand how dynamic programming can be applied to this problem?
question_mark
Can you explain why the solution involves recursive subproblems?
question_mark
Will you be able to efficiently calculate the Catalan number using a mathematical formula?

warning

常见陷阱

外企场景

error
Not memoizing the results of subproblems, leading to redundant calculations.
error
Incorrectly assuming that the solution can be computed in linear time without considering the complexity of recursive calls.
error
Failing to realize that the number of BSTs grows exponentially, which may lead to inefficiencies in time complexity if not optimized.

swap_horiz

进阶变体

外企场景

arrow_right_alt
How would the problem change if we allowed duplicate values in the BST?
arrow_right_alt
What happens if the BST formation is restricted by some additional constraints, like balanced height?
arrow_right_alt
How can this approach be adapted to count the number of unique AVL trees instead of BSTs?

help

常见问题

外企场景

继续练习

#95 不同的二叉搜索树 II #1569 将子数组重新排序得到同一个二叉搜索树的方案数 #98 验证二叉搜索树