NeetCode #447LC-96MediumTrees
← Back to All Problems#447 · #96 · Unique Binary Search Trees(不同的二叉搜索树)
📌 Problem Statement & Constraints
Given an integer
n, return the number of structurally unique binary search trees that store exactly n distinct values. Constraints: 1 <= n <= 19.💡 Core Algorithmic Approaches
- Fix the root: if it holds the
j-th smallest value, the left subtree hasjvalues and the right hasn - 1 - j. - The subtrees are independent, so the count is
sum over j of dp[j] * dp[n-1-j]. - This is the Catalan number recurrence, and it is exactly what
Unique Binary Search Trees IIenumerates. - The DP is O(n^2) time and O(n) space, versus the closed form which needs big-number division.
💻 Benchmark Python3 Implementation
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1 # the empty tree
for i in range(1, n + 1):
for j in range(i):
# j nodes on the left, i - 1 - j on the right
dp[i] += dp[j] * dp[i - 1 - j]
return dp[n]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): the double loop over the root choice and the tree size.
💾 Space Complexity
O(n) for the DP array.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting
dp[0] = 1: the recurrence would produce all zeros, since the empty subtree is a valid (and necessary) base case. - Using
dp[i-1-j]incorrectly: the right subtree hasi - 1 - jnodes, wherejis the left subtree size. - Returning a float: the closed form
C(2n, n) / (n + 1)involves division; the DP stays integral. - Confusing this with counting binary trees: the BST structure is determined by the values' order, so the shapes are what is being counted.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.