leetcode medium : Unique Binary Search Trees II
Unique Binary Search Trees II - LeetCode
Unique Binary Search Trees II - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
예전에 비슷한 문제를 본적이 있어서 어떻게 풀어야할지 바로 떠올렸다.
class Solution:
def helper(self, start, end):
if start > end:
return []
if start == end:
return [TreeNode(start)]
result = []
for head in range(start, end + 1):
left_trees = self.helper(start, head - 1)
right_trees = self.helper(head + 1, end)
if not left_trees:
for tree in right_trees:
h = TreeNode(head)
h.right = tree
result.append(h)
continue
if not right_trees:
for tree in left_trees:
h = TreeNode(head)
h.left = tree
result.append(h)
continue
for ltree in left_trees:
for rtree in right_trees:
h = TreeNode(head)
h.left = ltree
h.right = rtree
result.append(h)
return result
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
result = self.helper(1, n)
return result
시간복잡도가 근데.. .어느정도지?
다른 사람 솔루션 미쳤네 그냥
def generateTrees(self, n):
def node(val, left, right):
node = TreeNode(val)
node.left = left
node.right = right
return node
def trees(first, last):
return [node(root, left, right)
for root in range(first, last+1)
for left in trees(first, root-1)
for right in trees(root+1, last)] or [None]
return trees(1, n)
대단하다 ㅋㅋㅋ
음 근데 혹시 memoization 적용이 가능할까?
중복 무조건 있을거같은데 ㅋㅋ
class Solution:
def helper(self, start, end):
if start > end:
return []
if start == end:
return [TreeNode(start)]
if (start, end) in self.cache:
return self.cache[(start, end)]
result = []
for head in range(start, end + 1):
left_trees = self.helper(start, head - 1)
right_trees = self.helper(head + 1, end)
if not left_trees:
for tree in right_trees:
h = TreeNode(head)
h.right = tree
result.append(h)
continue
if not right_trees:
for tree in left_trees:
h = TreeNode(head)
h.left = tree
result.append(h)
continue
for ltree in left_trees:
for rtree in right_trees:
h = TreeNode(head)
h.left = ltree
h.right = rtree
result.append(h)
self.cache[(start, end)] = result
return result
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
self.cache = {}
result = self.helper(1, n)
return result
찢었다