不同二叉搜索树
2021-07-06 本文已影响0人
jojo1313
给一个整数 n ,请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
思路:枚举根节点值为 i,根据二叉搜索树的性质可知左子树的节点值的集合为 [1…i−1],右子树的节点值的集合为 [i+1…n]。
什么是二叉搜索树:
二叉搜索树根节点的值大于左子树所有节点的值,小于右子树所有节点的值,且左子树和右子树也同样为二叉搜索树。
def generateTrees(self, n):
def genTrees(start,end):
if start>end:
return [None,]
allTrees=[]
for i in range(start,end+1):
leftTrees=genTrees(start,i-1)
rightTrees=genTrees(i+1,end)
for l in leftTrees:
for r in rightTrees:
currTree=TreeNode(i)
currTree.left=l
currTree.right=r
allTrees.append(currTree)
return allTrees
return genTrees(1,n) if n else []