Question: https://oj.leetcode.com/problems/unique-binary-search-trees-ii/
Question Name: Unique Binary Search Trees II
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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param a list(representing trees) # @return the root node the tree def convertArray2Trees(self, array): result = [TreeNode(i+1) for i in xrange(len(array))] root = None for index in xrange(len(array)): if array[index] == -1: # This node has no father. It is the root node. root = result[index] else: if array[index] > index: # Its father is on the right side. Thus it is # father's left son. result[array[index]].left = result[index] else: # Its father is no the left side. result[array[index]].right = result[index] return root # @return a list of lists(representing trees) def generateArray(self, array, current, left, right): result = [] resultTemp = [] # Not possible to have any son. if left >= current and current >= right: return [array] # Fill the left son if left >= current: resultTemp = [array] else: for son in xrange(left, current): temp = array * 1 temp[son] = current resultTemp.extend(self.generateArray(temp, son, left, current-1)) # Fill the right son if current >= right: result = resultTemp else: for tempStatus in resultTemp: for son in xrange(current+1, right+1): temp = tempStatus * 1 temp[son] = current result.extend(self.generateArray(temp, son, current+1, right)) return result # @return a list of tree node def generateTrees(self, n): # Handle the special case. if n == 0: return [None] result = [] # We firstly generate the trees in form of array. # array[i] == j means, the i(th) node's father is j(th) node. (0-based) for root in xrange(n): temp = [-1] * n tempRes = self.generateArray(temp, root, 0, n-1) result.extend(tempRes) # Convert the arrays into trees. return [self.convertArray2Trees(array) for array in result] |
This is an ugly DP…