二叉搜索树心法（构造篇）

95. 不同的二叉搜索树 II https://leetcode.cn/problems/unique-binary-search-trees-ii

95. Unique Binary Search Trees II https://leetcode.com/problems/unique-binary-search-trees-ii

96. 不同的二叉搜索树 https://leetcode.cn/problems/unique-binary-search-trees

96. Unique Binary Search Trees https://leetcode.com/problems/unique-binary-search-trees

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	Difficulty
95. Unique Binary Search Trees II	🟠
96. Unique Binary Search Trees	🟠

Prerequisites

Before reading this article, you should first learn:

• Basics of Binary Tree Structure
• DFS/BFS Traversal of Binary Trees

Previously, I wrote two articles on practicing BST algorithm problems step-by-step. The first article discussed the significance of in-order traversal for BSTs, and the second article covered basic BST operations.

This article is the third in the step-by-step BST series, progressively explaining two problems on how to calculate all valid BSTs.

The first problem is LeetCode Problem 96 "Unique Binary Search Trees". Given a positive integer n, calculate the number of different BST structures that can be formed with values {1, 2, 3, ..., n}.

The function signature is as follows:

java 🟢

int numTrees(int n);

cpp 🤖

int numTrees(int n);

python 🤖

def numTrees(n: int) -> int:

go 🤖

func numTrees(n int) int {}

javascript 🤖

var numTrees = function(n) {

};

For example, if the input is n = 3, the algorithm returns 5 because there are 5 different BST structures that can store {1,2,3}:

This is a classic exhaustive enumeration problem. So, what method can correctly enumerate the number of valid BSTs?

As we mentioned earlier, don't underestimate "exhaustive enumeration." It seems simple, but it requires some technical skill. The key issue is to ensure you don't miss any possibilities or count too many. So, how do you do it?

In the previous Step-by-Step Binary Tree Series Part 1, we talked about the key to binary tree algorithms: clearly defining what the root node needs to do. Since a BST is a special kind of binary tree, the core idea is the same.

loading...