95题
输出所有可能的搜索二叉树
采用递归,不断地进行root和左右子节点的递归
class Solution(object):
def generateTrees(self, n):
if n == 0: return []
def helper(start,end):
res = []
if start > end:
res.append(None)
for val in range(start, end + 1):
left = helper(start, val - 1)
right = helper(val + 1,end)
for i in left:
for j in right:
root = TreeNode(val)
root.left = i
root.right = j
res.append(root)
return res
return helper(1, n)
96题采用动态规划
class Solution(object):
def numTrees(self, n):
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i + 1):
dp[i] += dp[j - 1] * dp[i - j]
return dp[-1]