Python generator solution


  • 3
    G

    credit goes to https://leetcode.com/discuss/3440/help-simplify-my-code-the-second-one?show=4884#a4884

    # Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        # @return a list of tree node
        # 2:30
        def generateTrees(self, n):
            nodes = map(TreeNode, range(1, n+1))
            return map(copy.deepcopy, self.buildTree(nodes))
    
        def buildTree(self, nodes):
            n = len(nodes)
            if n == 0:
                yield None
                return
    
            for i in range(n):
                root = nodes[i]
                for left in self.buildTree(nodes[:i]):
                    for right in self.buildTree(nodes[i+1:]):
                        root.left, root.right = left, right
                        yield root

  • 2
    M

    Very elegant pythonic code!!

    Actually, you don't need the deepcopy.

    def gen_trees(A):
        if A == []:
            yield None
            return
    
        for i in range(len(A)):
            for left in gen_trees(A[:i]):
                for right in gen_trees(A[i+1:]):
                    root = TreeNode(A[i])
                    root.left, root.right = left, right
                    yield root
    
    class Solution:
        # @param {integer} n
        # @return {TreeNode[]}
        def generateTrees(self, n):
            return list(gen_trees(range(1,n+1)))

Log in to reply
 

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