python, iterative, dfs, dfs


  • 0
    S
    class Solution(object):
        
        def getatree(self, listt):
            value = listt.pop()
            if value == 0:
                return None
            node = TreeNode(value)
            node.left = self.getatree(listt)
            node.right = self.getatree(listt)
            return node
            
            
        def generateTrees(self, n):
            """
            :type n: int
            :rtype: List[TreeNode]
            """
            if n == 0:
                return []
            theend = []
            paraluniverse = [([],[range(1,n+1)])]
            while paraluniverse:
                (history, future) = paraluniverse.pop()
                if future == []:
                    theend.append(history)
                    continue
                tomorrow = future.pop()
                if tomorrow == []:
                    history.append(0)
                    paraluniverse.append((history,future))
                else:
                    for i in range(len(tomorrow)):
                        afuture = future[:]
                        ahistory = history[:]
                        ahistory.append(tomorrow[i])
                        afuture.append(tomorrow[i+1:])
                        afuture.append(tomorrow[:i])
                        paraluniverse.append((ahistory,afuture))
    
            res = []
            for fullhistory in theend:
                fullhistory.reverse()
                res.append(self.getatree(fullhistory))
            return res
    

  • 0
    S
    This post is deleted!

Log in to reply
 

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