Recursive, use memory to speed up.


  • 0
    A
    def generateTrees(self, n):
        if not n:
        	return [None]
        mem={}
        def recur(start, end):
        	key=str(start)+'-'+str(end)
        	if key in mem:
        		return mem[key]
        	if start>end:
        		return [None]
        	mem.setdefault(key, [])
        	for i in range(start, end+1):
        		for left in recur(start, i-1):
        			for right in recur(i+1, end):
        				newNode=TreeNode(i)
        				newNode.left=left
        				newNode.right=right
        				mem[key]+=newNode,
        	return mem[key]
        recur(1, n)
        return mem[str(1)+'-'+str(n)]
    

    Here 'mem' keeps those trees that have already been built, where the keys are the combinations of start/end numbers. Sure enough it's gonna speed up the calculation. 呵呵


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.