給你一個(gè)整數(shù) n ，請(qǐng)你生成并返回所有由 n 個(gè)節(jié)點(diǎn)組成且節(jié)點(diǎn)值從 1 到 n 互不相同的不同 二叉搜索樹 。可以按 任意順序 返回答案。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii

例：

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

解析：

遞歸，分成左子樹和右子樹兩個(gè)子問題。

# 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]"""res = [] # 存放最終結(jié)果if n < 1:return reselse:return self.generateBST(1, n)def generateBST(self, start, end):res = [] # 存放臨時(shí)子樹if start > end:res.append(None)return reselse:for i in range(start, end + 1):# 左子樹left_tree = self.generateBST(start, i - 1) # 添加所有不同的左子樹# 右子樹right_tree = self.generateBST(i + 1, end) # 添加所有不同的右子樹for left in left_tree:for right in right_tree: # 左右子樹組合回到上一層的遞歸root = TreeNode(i)root.left = leftroot.right = rightres.append(root)return res # 返回上一層遞歸的左/右子樹結(jié)果

?

總結(jié)

以上是生活随笔為你收集整理的不同的二叉搜索树 IIPython解法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。