LeetCode 96: Unique Binary Search Trees (Catalan DP)

2026-03-18 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 96Dynamic ProgrammingCatalan Number

Today we solve LeetCode 96 - Unique Binary Search Trees.

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

LeetCode 96 Catalan DP split-by-root diagram

English

Problem Summary

Given an integer n, count how many structurally unique BSTs can be formed using values 1..n.

Key Insight

Pick each value root as the root once. Then left subtree uses root-1 nodes, right subtree uses n-root nodes. Their combinations multiply.

Brute Force and Limitations

Brute force would recursively generate all tree structures, which grows explosively and does a lot of repeated counting.

Optimal Algorithm Steps

1) Let dp[i] be number of unique BSTs with i nodes.
2) Base: dp[0] = 1 (empty tree), dp[1] = 1.
3) For each nodes = 2..n, enumerate root = 1..nodes.
4) Add dp[root-1] * dp[nodes-root] to dp[nodes].
5) Answer is dp[n].

Complexity Analysis

Time: O(n^2).
Space: O(n).

Common Pitfalls

- Forgetting dp[0] = 1, which breaks multiplicative counting.
- Using wrong right-size index: must be nodes-root.
- Mixing node count with value range boundaries.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int nodes = 2; nodes <= n; nodes++) {
            int ways = 0;
            for (int root = 1; root <= nodes; root++) {
                ways += dp[root - 1] * dp[nodes - root];
            }
            dp[nodes] = ways;
        }

        return dp[n];
    }
}

func numTrees(n int) int {
    dp := make([]int, n+1)
    dp[0] = 1
    if n >= 1 {
        dp[1] = 1
    }

    for nodes := 2; nodes <= n; nodes++ {
        ways := 0
        for root := 1; root <= nodes; root++ {
            ways += dp[root-1] * dp[nodes-root]
        }
        dp[nodes] = ways
    }

    return dp[n]
}

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        if (n >= 1) dp[1] = 1;

        for (int nodes = 2; nodes <= n; ++nodes) {
            int ways = 0;
            for (int root = 1; root <= nodes; ++root) {
                ways += dp[root - 1] * dp[nodes - root];
            }
            dp[nodes] = ways;
        }

        return dp[n];
    }
};

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        if n >= 1:
            dp[1] = 1

        for nodes in range(2, n + 1):
            ways = 0
            for root in range(1, nodes + 1):
                ways += dp[root - 1] * dp[nodes - root]
            dp[nodes] = ways

        return dp[n]

var numTrees = function(n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  if (n >= 1) dp[1] = 1;

  for (let nodes = 2; nodes <= n; nodes++) {
    let ways = 0;
    for (let root = 1; root <= nodes; root++) {
      ways += dp[root - 1] * dp[nodes - root];
    }
    dp[nodes] = ways;
  }

  return dp[n];
};

中文

题目概述

给定整数 n，使用值 1..n 作为节点，问一共有多少种结构不同的二叉搜索树。

核心思路

枚举每个值作为根节点。若根为 root，左子树有 root-1 个节点，右子树有 n-root 个节点。左右组合数量相乘，再对所有根求和。

暴力解法与不足

暴力可以递归生成所有树结构，但状态重复非常多，随着 n 增大，开销会迅速失控。

最优算法步骤

1）定义 dp[i] 表示 i 个节点能形成的不同 BST 数量。
2）初始化：dp[0] = 1（空树算一种），dp[1] = 1。
3）遍历 nodes = 2..n。
4）对每个根 root = 1..nodes，累加 dp[root-1] * dp[nodes-root]。
5）最终返回 dp[n]。

复杂度分析

时间复杂度：O(n^2)。
空间复杂度：O(n)。

常见陷阱

- 忘记设置 dp[0] = 1，会导致计数全错。
- 右子树节点数下标写错，应是 nodes-root。
- 将“节点数量”与“节点值区间”混淆。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int nodes = 2; nodes <= n; nodes++) {
            int ways = 0;
            for (int root = 1; root <= nodes; root++) {
                ways += dp[root - 1] * dp[nodes - root];
            }
            dp[nodes] = ways;
        }

        return dp[n];
    }
}

func numTrees(n int) int {
    dp := make([]int, n+1)
    dp[0] = 1
    if n >= 1 {
        dp[1] = 1
    }

    for nodes := 2; nodes <= n; nodes++ {
        ways := 0
        for root := 1; root <= nodes; root++ {
            ways += dp[root-1] * dp[nodes-root]
        }
        dp[nodes] = ways
    }

    return dp[n]
}

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        if (n >= 1) dp[1] = 1;

        for (int nodes = 2; nodes <= n; ++nodes) {
            int ways = 0;
            for (int root = 1; root <= nodes; ++root) {
                ways += dp[root - 1] * dp[nodes - root];
            }
            dp[nodes] = ways;
        }

        return dp[n];
    }
};

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        if n >= 1:
            dp[1] = 1

        for nodes in range(2, n + 1):
            ways = 0
            for root in range(1, nodes + 1):
                ways += dp[root - 1] * dp[nodes - root]
            dp[nodes] = ways

        return dp[n]

var numTrees = function(n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  if (n >= 1) dp[1] = 1;

  for (let nodes = 2; nodes <= n; nodes++) {
    let ways = 0;
    for (let root = 1; root <= nodes; root++) {
      ways += dp[root - 1] * dp[nodes - root];
    }
    dp[nodes] = ways;
  }

  return dp[n];
};