python - unique bst II


  • 0
    S
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        
        def copy(self, root):
            ret = None
            if root:
                ret = TreeNode(root.val)
                ret.left = self.copy(root.left)
                ret.right = self.copy(root.right)
            return ret
        
        def insert(self, root, curr, ht):
            
            # special insert routine assumes
            # that number to be inserted is greater
            # than all numbers in the tree
            level, ret, prev = 0, self.copy(root), None
            while level < ht:
                prev, level = prev.right if prev else ret, level + 1
            
            curr.left = prev.right if prev else ret
            if prev:
                prev.right = curr
            else:
                ret = curr
            
            return ret        
            
        def is_leaf(self, node):
            return node.left == None and node.right == None
        
        def generateTrees(self, n):
            """
            :type n: int
            :rtype: List[TreeNode]
            """
            answer = []
            if not n:
                return answer
            
            answer = [TreeNode(1)]
            
            for i in range(2,n+1):            
                scratch = []
                
                for tree in answer:
                    curr, ht = TreeNode(i), 0
                    scratch.append(self.insert(tree, curr, ht))
                    
                    # add the next greatest number into a tree from
                    # existing set of trees. start from the root
                    # and trickle it down to the last level.
                    # the next greatest number will be the right most leaf.
                    # use a copy-on-write approach for each insertion into
                    # the tree. insert the number into a copy of the tree.
                    while not self.is_leaf(curr):
                        curr, ht = TreeNode(i), ht + 1
                        scratch.append(self.insert(tree, curr, ht))
                
                answer = scratch
            
            return answer
                        
    

Log in to reply
 

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