LeetCode题解95.unique-binary-search-trees-ii

题目地址（95. 不同的二叉搜索树 II）

https://leetcode-cn.com/problems/unique-binary-search-trees-ii/description/

题目描述

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

思路

这是一个经典的使用分治思路的题目。基本思路和96.unique-binary-search-trees一样。

只是我们需要求解的不仅仅是数字，而是要求解所有的组合。我们假设问题 f(1, n) 是求解 1 到 n（两端包含）的所有二叉树。那么我们的目标就是求解 f(1, n)。

我们将问题进一步划分为子问题，假如左侧和右侧的树分别求好了，我们是不是只要运用组合的原理，将左右两者进行做和就好了，我们需要两层循环来完成这个过程。

关键点解析

• 分治法

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if not n:
            return []

        def generateTree(start, end):
            if start > end:
                return [None]
            res = []
            for i in range(start, end + 1):
                ls = generateTree(start, i - 1)
                rs = generateTree(i + 1, end)
                for l in ls:
                    for r in rs:
                        node = TreeNode(i)
                        node.left = l
                        node.right = r
                        res.append(node)

            return res

        return generateTree(1, n)

相关题目

• 96.unique-binary-search-trees

LeetCode题解212.word-search-ii

题目地址（212. 单词搜索 II） https://leetcode-cn.com/problems/word-search-ii/description/ 题目描述 给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平…

LeetCode题解501.Find-Mode-in-Binary-Search-Tree

Problem on Leetcode https://leetcode.com/problems/find-mode-in-binary-search-tree/ Description Given a binary search tree (BST) with duplicates, find all the mode(s) (the most freq…

LeetCode题解240.search-a-2-d-matrix-ii

题目地址 https://leetcode.com/problems/search-a-2d-matrix-ii/description/ 题目描述 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following …

LeetCode题解212. 单词搜索 II

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。示例:输入: words = ["oath","pea","eat","rain"] and bo…

LeetCode题解45.跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例:输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。  从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。说明:假设你总是可以到达数…