题目链接：Path Sum II | LeetCode OJ
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
Tags: Depth-first Search
分析
深度优先遍历题目，在Path Sum的基础上需要可行的解全部列出来。这里会用到有些动态规划的题目中也会用到的技巧，每次深度优先遍历时，都逐级传递从根结点到当前结点的路径path，如果发现当前结点是叶子结点且满足路径之和与期望相等，就把这个路径存入结果result。深度优先遍历仍然进行，不会因为发现了一条符合要求的路径而停止。
这道题的示例中我用到了Python的数组加法，数组加法不同于集合操作，相同的元素不会合并，元素的顺序也不会被打乱。例如[2,1] + [2,3] = [2,1,2,3]而不是[1,2,3]
示例
class Solution:
# @param root, a tree node
# @param sum, an integer
# @return a list of lists of integers
def pathSum(self, root, sum):
return self._pathSum(root, sum, [], [])
def _pathSum(self, root, sum, path, result):
if root is None:
return result
if sum == root.val and root.left is None and root.right is None:
return result + [path + [root.val]]
else:
return self._pathSum(root.left, sum - root.val, path + [root.val], result) + self._pathSum(root.right, sum - root.val, path + [root.val], result)
Leetcode 笔记系列的Python代码共享在https://github.com/wizcabbit/leetcode.solution