Short python solution


  • 13
    X
    class Solution:
    
    def pathSum(self, root, sum):
        if not root: return []
        if root.left == None and root.right == None:
            if sum == root.val: 
                return [[root.val]]
            else: 
                return []
        a = self.pathSum(root.left, sum - root.val) + \
            self.pathSum(root.right, sum - root.val)
        return [[root.val] + i for i in a]

  • 0

    That causes "IndentationError".


  • 5

    A bit shorter, by extracting the value and children into variables and some other stuff.

    class Solution:
        def pathSum(self, root, sum):
            if not root: return []
            v, C = root.val, (root.left, root.right)
            if any(C): return [[v] + i for c in C for i in self.pathSum(c, sum - v)]
            return [[v]] * (sum == v)

  • 0
    X

    Looks great. I guess it must comes from a lot of good habits to be able to write code as neat as this.


  • 3

    Thanks, although I really just tried to be short here, I wouldn't call it good. It's not very readable and the [[v]] * (sum == v) trick is a bit wasteful (though it doesn't matter much). Except for the size, I like this version a lot better:

    class Solution:
        def pathSum(self, root, sum):
            if not root:
                return []
            val, kids = root.val, (root.left, root.right)
            if any(kids):
                return [[val] + path
                        for kid in kids
                        for path in self.pathSum(kid, sum - val)]
            return [[val]] if val == sum else []

  • 0
    T

    This code is wonderful and I really learn a lot from it! Thank you!


  • 5
    C

    Nice answer, while it seems we can shorten it as:

    def pathSum(self, root, sum):
        if not root:
            return []
        if not root.left and not root.right and sum == root.val:
            return [[root.val]]
        tmp = self.pathSum(root.left, sum-root.val) + self.pathSum(root.right, sum-root.val)
        return [[root.val]+i for i in tmp]

  • 0
    W

    @xiangzhou.chen.5

    舟哥。。。递归很慢的。。


  • 0
    O

    @StefanPochmann

    1-liner:

    class Solution(object):
        def pathSum(self, root, sum):
            return [] if not root else [[root.val]+l for kid in [root.left, root.right] for l in self.pathSum(kid, sum-root.val)] if root.left or root.right else [[root.val]]*(sum==root.val)
    

    Then I realized you already had all the ideas, and all the fun : )


Log in to reply
 

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