5 lines recursive Python


  • 44
    def binaryTreePaths(self, root):
        if not root:
            return []
        return [str(root.val) + '->' + path
                for kid in (root.left, root.right) if kid
                for path in self.binaryTreePaths(kid)] or [str(root.val)]

  • 0
    W

    very nice. You always have nice and clean solution!


  • 2
    T

    Hi Stefan,
    This is the second time I have seen you using recursion in python like this, the first time was in different ways to add parenthesis, where you did:

    def diffWaysToCompute(self, input):
        return [a+b if c == '+' else a-b if c == '-' else a*b
                for i, c in enumerate(input) if c in '+-*'
                for a in self.diffWaysToCompute(input[:i])
                for b in self.diffWaysToCompute(input[i+1:])] or [int(input)]
    

    I am learning a lot from you. I just want to ask you if there are any tricks or guidelines for coming up with super concise recursion code like these?


  • 6

    Sorry, I think it's mainly experience and obsession :-)

    Though for Python in particular, I learned quite a bit by looking at solutions of others on CheckiO and by spending a month answering Python questions on StackOverflow and reading answers of others. And I experiment a lot, trying to improve my code further and further. Feedback for solutions I posted myself on those sites also helped.

    The "different ways to add parenthesis" might actually be a bad example, as I compute the same self.diffWaysToCompute(input[i+1:]) for every a. It might be better to do a for-loop for i, in which you first get all possibilities for a and b and only then combine them. Or use itertools.product. I say "might" because I'm not sure recomputation actually makes a real difference. Anyway, that would make the code longer, so I didn't. But that means my obsession with short/simple code might cause inefficiency there.


  • 0
    D

    Could you explain the syntax in your return statement? I've never seen two consecutive for statements like that.


  • 0

    That's not two for statements. There's no for statement at all there. It's a list comprehension with two for clauses. If you don't know list comprehensions, you should definitely learn them, they're great. Follow that link for some good explanation and examples.


  • 1
    W

    Very good answer!! Could you please explain why "or [str(root.val)]" is necessary ? Thanks!


  • 1

    Without that, I'd return an empty path list for leaf nodes. Which is wrong by itself, and it would also lead to every path list being empty.


  • 0
    S

    Thanks a lot! I always learn from your solution!


  • 0

    Sorry,could you use more simple code to explain this algorithm.I can't unstande it clearly
    Thank you!


  • 1
    C

    Technically, your solution is only 3 lines!!! Cool!!!
    I came up with a similar solution (list comprehension), but yours is shorter. The "or [str(root.val)]" is great!

    def binaryTreePaths(self, root):
        if not root:
            return []
        if not root.left and not root.right:
                return [str(root.val)]
        return [str(root.val)+"->" + i for sub in (root.left, root.right)
                for i in self.binaryTreePaths(sub) if sub]

  • 0
    R

    Nice work! Impressive.

    I would recommend you replace str(root.val) + '->' + path by "%s->%s"%(str(root.val) ,path), which could improve its efficiency.

    Thanks a lot


  • 0

    @cmc thanks, your answer is easy to understand.~


  • 2
    S

    Easy to understand Python

    def rootToLeafPaths(self, root):
       if not root: return []
       if not root.left and not root.right: return [str(root.val)]
       return [str(root.val) + '->' + i for i in self.rootToLeafPaths(root.left)] +
                 [str(root.val) + '->' + i for i in self.rootToLeafPaths(root.right)]
    

  • 1
    S

    Though your code is short, it is not that understandable.


  • 0
    J

    @simonzheng1234 agree! This piece code is really annoying.


  • 0

    @simonzheng1234 @jz678 Why? I think it's about as straight-forward as it gets. How would you in your opinion improve it?


  • 0
    J

    @StefanPochmann I'm sorry if I sound rude. I'm new to python, and not familiar with the syntax. I felt frustrated yesterday that's why I left this comment. Really sorry!

    for kid in (root.left, root.right) if kid
    for path in self.binaryTreePaths(kid)] or [str(root.val)]
    Do you mind explaining these two statements?


  • 1

    @jz678 Haha, I considered saying "Maybe you just don't know Python well?" but decided against it :-P

    Anyway, learn about "list comprehensions", then it should be easy. I'm just going through the root's children and their paths and prepend the root to them.


Log in to reply
 

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