Question: https://oj.leetcode.com/problems/path-sum-ii/
Question Name: Path Sum II
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param root, a tree node # @param sum, an integer # @return a boolean def pathSum(self, root, sum): if root == None: # Empty tree will always result in False return [] elif root.left == None and root.right == None: # Reach the leaf. if root.val == sum: return [[root.val]] else: return [] elif root.left == None: # Only has right child. result = self.pathSum(root.right, sum-root.val) return [[root.val] + item for item in result] elif root.right == None: # Only has left child. result = self.pathSum(root.left, sum-root.val) return [[root.val] + item for item in result] else: # Has two children. result = self.pathSum(root.left, sum-root.val) result.extend(self.pathSum(root.right, sum-root.val)) return [[root.val] + item for item in result] |