Unique Binary Search Tree II @ LeetCode (Python)
kitt
posted @ 2014年2月18日 16:51
in LeetCode
, 3828 阅读
递归, 对于[start, end]范围内的每个节点, 产生所有可能的左、右子树, 再产生(#左子树 x #右子树)棵树, 返回所有的root nodes。gen函数返回一个list of root nodes, 每个root node所表示的树是由[start, end]这个范围内的数构成的BST。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | # class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: # @return a list of tree node def generateTrees(self, n): return self.gen(1, n) def gen(self, start, end): # return a list containing all root nodes of BSTs constructed from [start, end] if start > end: return [None] res = [] for rootVal in xrange(start, end + 1): leftList = self.gen(start, rootVal - 1) rightList = self.gen(rootVal + 1, end) for i in leftList: for j in rightList: root = TreeNode(rootVal) root.left = i root.right = j res.append(root) return res |
2015年5月30日 19:42
好厉害啊........!!!