What is the best approach for generating all unique BSTs for n nodes?

Use recursive tree construction with backtracking to explore all left and right subtree combinations, ensuring each root selection covers every unique BST arrangement.

How does backtracking prevent duplicate trees in Unique Binary Search Trees II?

Backtracking restores previous recursion states after exploring a root's subtrees, preventing state contamination and ensuring each root produces all valid combinations independently.

Can dynamic programming optimize Unique Binary Search Trees II?

Yes, memoization stores previously computed subtrees for value ranges, reducing redundant recursion calls and improving efficiency while generating all unique BSTs.

What is the expected time and space complexity?

Time complexity is O(\frac{4^n}{\sqrt{n}}) due to Catalan number growth, and space complexity is O(\sum_{k=1}^{n}\frac{4^k}{\sqrt{k}}) for storing generated trees and recursion stack.

Are there common pitfalls when implementing Unique Binary Search Trees II?

Yes, common mistakes include not combining all left-right subtree pairs, failing to reset recursive state, and omitting memoization leading to redundant calculations.

#95

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

不同的二叉搜索树 II

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同二叉搜索树。可以按任意顺序返回答案。示例 1：输入： n = 3 输出： [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3…

动态规划回溯树二叉搜索树二叉树

题目描述

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 8

lightbulb

解题思路

方法一：DFS

我们设计一个函数 $dfs(i, j)$ ，返回由 $[i, j]$ 组成的所有可行的二叉搜索树，那么答案就是 $dfs(1, n)$ 。

函数 $dfs(i, j)$ 的执行步骤如下：

如果 $i > j$ ，那么说明此时没有数字可以构成二叉搜索树，返回由一个空节点组成的列表。
如果 $i \leq j$ ，那么我们枚举 $[i, j]$ 中的数字 $v$ 作为根节点，那么根节点 $v$ 的左子树由 $[i, v - 1]$ 组成，右子树由 $[v + 1, j]$ 组成，最后将左右子树的所有组合笛卡尔积，即 $left \times right$ ，加上根节点 $v$ ，得到以 $v$ 为根节点的所有二叉搜索树。

时间复杂度 $O(n \times G(n))$ ，空间复杂度 $O(n \times G(n))$ 。其中 $G(n)$ 是卡特兰数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        def dfs(i: int, j: int) -> List[Optional[TreeNode]]:
            if i > j:
                return [None]
            ans = []
            for v in range(i, j + 1):
                left = dfs(i, v - 1)
                right = dfs(v + 1, j)
                for l in left:
                    for r in right:
                        ans.append(TreeNode(v, l, r))
            return ans

        return dfs(1, n)

speed

复杂度分析

指标	值
时间	O(\dfrac{4^n}{\sqrt{n}})
空间	O(\sum_{k=1}^{n}\dfrac{4^k}{{\sqrt{k}}})

psychology

面试官常问的追问

外企场景

question_mark
Do you consider every integer as a potential root when generating BSTs?
question_mark
Can you explain how backtracking ensures all unique subtree combinations are explored?
question_mark
Will you optimize repeated subtree calculations with memoization for efficiency?

warning

常见陷阱

外企场景

error
Failing to combine all left and right subtree pairs for each root, leading to missing BSTs.
error
Not resetting recursive state between root selections, causing duplicate or incorrect tree structures.
error
Neglecting to memoize subtrees, resulting in exponential redundant computations and stack overflow for larger n.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Generate the number of unique BSTs (Unique Binary Search Trees I) instead of all structures.
arrow_right_alt
Return all unique BSTs with a given pre-order traversal constraint.
arrow_right_alt
Modify the BST generation to support duplicate values while maintaining valid BST rules.

help

常见问题

外企场景

继续练习

#96 不同的二叉搜索树 #98 验证二叉搜索树 #99 恢复二叉搜索树