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
My code:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n==0:
return []
self.final=self.Set_node(1,n)
return self.final
def Set_node(self,start,end):
if start>end:
return [None,]
all_trees=[]
for i in range(start,end+1):
left_trees=self.Set_node(start,i-1)
right_trees=self.Set_node(i+1,end)
for l in left_trees:
for r in right_trees:
current=TreeNode(i)
current.left=l
current.right=r
all_trees.append(current)
return all_trees
Solution: https://leetcode.com/problems/unique-binary-search-trees-ii/