Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Definition for a binary tree node.
- # class TreeNode:
- # def __init__(self, val=0, left=None, right=None):
- # self.val = val
- # self.left = left
- # self.right = right
- # Definition for a binary tree node.
- # class TreeNode:
- # def __init__(self, val=0, left=None, right=None):
- # self.val = val
- # self.left = left
- # self.right = right
- class Solution:
- def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
- dp = {}
- def generate(left, right):
- if left > right:
- return [None]
- if (left, right) in dp:
- return dp[(left, right)]
- res = []
- for val in range(left, right + 1):
- leftTrees = generate(left, val - 1)
- rightTrees = generate(val + 1, right)
- for l in leftTrees:
- for r in rightTrees:
- root = TreeNode(val)
- root.left = l
- root.right = r
- res.append(root)
- dp[(left, right)] = res
- return res
- if n == 0:
- return []
- return generate(1, n)
Advertisement