Unique Binary Search

2025-05-02

leetcode, unique_binary_search

Given an integer n, return the number of structurally unique **BST’**s (binary search trees) which has exctly n nodes unique values from 1 to n.

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

unique_binary_search.png

二叉搜索树(Binary Search Tree, BST)数据结构

定义：

  • 对于每个节点，其左子树中的所有节点值均小于该节点值。
  • 对于每个节点，其右子树中的所有节点值均大于该节点值。
  • 左右子树本身也必须是二叉搜索树。

特性：

  • 中序遍历有序：对BST进行中序遍历，得到的节点值是递增的。
  • 查找效率高：在理想情况下(平衡的)，查找、插入、删除的时间复杂度为O(log n)。

图示中，当n为3时，以1为根节点有2种；以2为根节点有1种；以3为根节点有3种。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;  // 空树
        dp[1] = 1;  // 只有一个节点
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <=i; j++) {
                dp[i] += dp[j - 1] * dp [i - j];
            }
        }
        return dp[n];
    }
}

从数学的归纳法分析：
当n=0时为空树，G(0)=1
当n=1时只有一个节点，G(1)=1
当n=2时，截取图示中的结果，G(2)=2
当n=3时，