# 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]