leetcode113 Path Sum II

  1 """
  2 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
  3 Note: A leaf is a node with no children.
  4 Example:
  5 Given the below binary tree and sum = 22,
  6       5
  7      / 
  8     4   8
  9    /   / 
 10   11  13  4
 11  /      / 
 12 7    2  5   1
 13 Return:
 14 [
 15    [5,4,11,2],
 16    [5,8,4,5]
 17 ]
 18 """
 19 """
 20 此题好题：写三种解法
 21 解法一：recursive
 22 """
 23 class TreeNode:
 24     def __init__(self, x):
 25         self.val = x
 26         self.left = None
 27         self.right = None
 28 class Solution1:
 29     def pathSum(self, root, sum):
 30         if not root:
 31             return []
 32         res = []
 33         path = []
 34         self.recursive(root, res, sum, path)
 35         return res
 36     def recursive(self, root, res, sum, path):
 37         if not root.left and not root.right and sum == root.val:
 38             path.append(root.val)
 39             res.append(path)
 40         if root.left:
 41             self.recursive(root.left, res, sum-root.val, path+[root.val])
 42         if root.right:
 43             self.recursive(root.right, res, sum-root.val, path+[root.val])
 44 """
 45 解法二：DFS
 46 """
 47 class Solution2:
 48     def pathSum(self, root, s): #注意这里,将原本的sum改为s了
 49         if not root:
 50             return []
 51         stack = []
 52         res = []
 53         stack.append((root, [root.val]))
 54         while stack:
 55             root, path = stack.pop()
 56             if not root.left and not root.right and sum(path) == s: #！！！关键点
 57                 res.append(path)
 58             if root.left:
 59                 stack.append((root.left, path+[root.left.val]))
 60             if root.right:
 61                 stack.append((root.right, path+[root.right.val]))
 62         return res
 63 """
 64 解法三：BFS
 65 """
 66 class Solution3:
 67     def pathSum(self, root, s):
 68         if not root:
 69             return []
 70         queue = []
 71         res = []
 72         queue.append((root, [root.val]))
 73         while queue:
 74             root, path = queue.pop(0)  #队列和栈的区别在这
 75             if not root.left and not root.right and sum(path) == s:
 76                 res.append(path)
 77             if root.left:
 78                 queue.append((root.left, path+[root.left.val]))
 79             if root.right:
 80                 queue.append((root.right, path+[root.right.val]))
 81         return res
 82 if __name__ == '__main__':
 83     l1 = TreeNode(5)
 84     l2 = TreeNode(4)
 85     l3 = TreeNode(8)
 86     l4 = TreeNode(11)
 87     l5 = TreeNode(5)
 88     l6 = TreeNode(13)
 89     l7 = TreeNode(4)
 90     l8 = TreeNode(7)
 91     l9 = TreeNode(2)
 92     l10 = TreeNode(1)
 93     l1.left = l2
 94     l1.right = l3
 95     l2.left = l4
 96     l3.left = l6
 97     l3.right = l7
 98     l7.left = l5
 99     l4.left = l8
100     l4.right = l9
101     l7.right = l10
102     ans = Solution3()
103     print(ans.pathSum(l1, 22))