0095：不同的二叉搜索树 II（★）

2015-04-05 约 252 字预计阅读 1 分钟次阅读

力扣第 95 题

题目

给你一个整数 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

分析

令 dfs(i,j) 代表节点值 i 到 j 组成的不同二叉搜索树，即可递归。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        def dfs(i,j):
            if i>j:
                return [None]
            res = []
            for k in range(i,j+1):
                for l in dfs(i,k-1):
                    for r in dfs(k+1,j):
                        res.append(TreeNode(k,l,r))
            return res
        return dfs(1,n)

56 ms

目录

0095：不同的二叉搜索树 II（★）

题目

分析

解答