1、题目描述

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

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

相关题：96. 不同的二叉搜索树（多少种） https://blog.csdn.net/IOT_victor/article/details/107066267

2、代码详解

递归法

# Definition for a binary tree node. class TreeNode(object): def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution(object): def generateTrees(self, n): """ :type n: int :rtype: List[TreeNode] """ if n == 0: return [] return self.dfs(1, n) def dfs(self, start, end): if start > end: return [None] res = [] for rootval in range(start, end + 1): # 选一个root LeftTree = self.dfs(start, rootval - 1) # 左子树所有可能 RightTree = self.dfs(rootval + 1, end) # 右子树所有可能 # 连接在一起 for i in LeftTree: for j in RightTree: root = TreeNode(rootval) root.left = i root.right = j res.append(root) return res

https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode/