My Simple Easy to understand Python Solution, beats 88%.


  • 0
    H
    class Solution(object):
        def generateTreesHelper(self, n, less_than, greater_than):
            """
            :type n: int
            :type less_than: int
            :type greater_than: int
            :rtype: List[TreeNode]
            """
            rst = []
            for i in xrange(1 if greater_than == - 1 else greater_than + 1,
                            n + 1 if less_than == -1 else less_than):  # Suppose first node value is i.
                left_list = self.generateTreesHelper(n, i, greater_than)
                right_list = self.generateTreesHelper(n, less_than, i)
                if not right_list:
                    for l_tree in left_list:
                        new_node = TreeNode(i)
                        new_node.left = l_tree
                        rst.append(new_node)
                if not left_list:
                    for r_tree in right_list:
                        new_node = TreeNode(i)
                        new_node.right = r_tree
                        rst.append(new_node)
                if left_list and right_list:
                    for l_tree in left_list:
                        for r_tree in right_list:
                            new_node = TreeNode(i)
                            new_node.left = l_tree
                            new_node.right = r_tree
                            rst.append(new_node)
                if not left_list and not right_list:
                    new_node = TreeNode(i)
                    rst.append(new_node)
    
            return rst
    
        def generateTrees(self, n):
            """
            :type n: int
            :rtype: List[TreeNode]
            """
            return self.generateTreesHelper(n, -1, -1)
    
    

    The solution is basically using recursion to keep generating new nodes which left child is a BST, and a right child is a BST, but we need to check if left child or right child does not exist such solution. But if both left and right child has a solution, we can simply creating result lists which composed of a new node which left and right child is also a BST.


Log in to reply
 

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