Should-be-6-Liner


  • 48

    If only LeetCode had a TreeNode(val, left, right) constructor... sigh. Then I wouldn't need to provide my own and my solution would be six lines instead of eleven.

    def generateTrees(self, n):
        def node(val, left, right):
            node = TreeNode(val)
            node.left = left
            node.right = right
            return node
        def trees(first, last):
            return [node(root, left, right)
                    for root in range(first, last+1)
                    for left in trees(first, root-1)
                    for right in trees(root+1, last)] or [None]
        return trees(1, n)
    

    Or even just four lines, if it's not forbidden to add an optional argument:

    def node(val, left, right):
        node = TreeNode(val)
        node.left = left
        node.right = right
        return node
    
    class Solution:
        def generateTrees(self, last, first=1):
            return [node(root, left, right)
                    for root in range(first, last+1)
                    for left in self.generateTrees(root-1, first)
                    for right in self.generateTrees(last, root+1)] or [None]
    

    Just another version, using loops instead of list comprehension:

    def generateTrees(self, n):
        def generate(first, last):
            trees = []
            for root in range(first, last+1):
                for left in generate(first, root-1):
                    for right in generate(root+1, last):
                        node = TreeNode(root)
                        node.left = left
                        node.right = right
                        trees += node,
            return trees or [None]
        return generate(1, n)

  • 0
    O

    OMG, always learn a lot from your code! Plz keep posting! Really appreciate it!


  • 0
    L

    Love this concise code. Few people can their code clean and effective at the mean time.


  • 0

    @1337c0d3r shouldn't we add the possibility to initialize left and right pointers in the TreeNode constructor? I was trying to do what Stefan was doing with list comprehension but got frustrated cause we can't do that.


  • -1
    D

    Can we ask Admin group to update the interface of TreeNode like this.

    class TreeNode:
        def __init__(self, x, left=None, right=None):
            self.val = x
            self.left = left
            self.right = right
    

  • 0
    Z

    @StefanPochmann said in Should-be-6-Liner:

    node,

    Could you please explain what the comma indicates. Thank you.


  • 0

    @zeusidkz A tuple.


  • 0

    What is the time complexity?


  • 0
    G

    I think we should use copy.deepcopy to generate a new subtree for each new root for safety. But it can not pass the OJ ...


  • 0

    @SamuraiLucifer said in Should-be-6-Liner:

    But it can not pass the OJ ...

    Why not?


  • 0
    G

    @StefanPochmann TLE at the last input, where n = 8


  • 0

    @SamuraiLucifer The following easily gets accepted (in about 500-600 ms):

    def generateTrees(self, n):
        if n == 0: return []
        def node(val, left, right):
            node = TreeNode(val)
            node.left = left
            node.right = right
            return node
        def trees(first, last):
            return [node(root, copy.deepcopy(left), right)
                    for root in range(first, last+1)
                    for left in trees(first, root-1)
                    for right in trees(root+1, last)] or [None]
        return trees(1, n)

  • 0
    G

    @StefanPochmann Oh, yes, since we don't need to copy right children. Thanks !


  • 0
    L

    WOW!!!AMAZING!!!


  • 0
    F

    Why not add a cache?

    class Solution(object):
        def generateTrees(self, n):
            if n < 1: return []
            cache = {}
            def generate(first, last):
                if first > last: return [None]
                if (first, last) in cache: return cache[first, last]
                trees = []
                for root in range(first, last+1):
                    for left in generate(first, root-1):
                        for right in generate(root+1, last):
                            node = TreeNode(root)
                            node.left = left
                            node.right = right
                            trees += node,
                cache[first, last] = trees
                return trees
            return generate(1, n)
    

  • 0

    @FindRX said in Should-be-6-Liner:

    Why not add a cache?

    Because I don't need to.


  • 0
    F

    @StefanPochmann
    You mean the code without cache is more readable?
    or the improvement is minor so it's not necessary?


  • 0

    @FindRX I mean I don't need to add a cache because it's easily fast enough to be accepted without caching.


  • 0
    F

    @StefanPochmann
    Get your point.


  • 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.