Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Solution:
# Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @return a list of tree node def generateTrees(self, n): return self.generateTrees2(1,n) def generateTrees2(self, begin, end): solution = [] if begin > end: solution.append(None) return solution for root in range(begin,end+1): leftNodes = self.generateTrees2(begin, root-1) rightNodes = self.generateTrees2(root+1, end) for leftNode in leftNodes: for rightNode in rightNodes: node = TreeNode(root) node.left = leftNode node.right = rightNode solution.append(node) return solution
No comments :
Post a Comment