[LeetCode] 095. Unique Binary Search Trees II *
-
date_range April 16, 2019 - Tuesday info
Problem (Medium)
095. Unique Binary Search Trees II
Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.
Example:
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation: The above output corresponds to the 5 unique BST’s shown below:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Approach 1: Recursive Solution *
Idea
Solution
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n == 0:
return []
return self.dfs(1, n+1)
def dfs(self, start, end):
if start == end:
return None
result = []
for i in xrange(start, end):
for l in self.dfs(start, i) or [None]:
for r in self.dfs(i+1, end) or [None]:
node = TreeNode(i)
node.left, node.right = l, r
result.append(node)
return result
Complexity
- Time: $O()$
- Space: $O()$
KF