Given an integer n, Build all by 1 … n A binary search tree made up of nodes .
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]
]
explain :
The above output corresponds to the following 5 Binary search trees with different structures ：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
This question is an extension of the previous one , The idea is roughly the same , Use recursion to build left and right subtrees . Notice the range of the left and right subtrees .
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if n == 0:
return []
return self.buildBst(1,n)
def buildBst(self,begin,end):
result = []
if end < begin:
result.append(None)
for i in range(begin,end+1):
for left in self.buildBst(begin,i-1):
for right in self.buildBst(i+1,end):
root = TreeNode(i)
root.left = left
root.right = right
result.append(root)
return result