题目
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
思路
递归查找,每个节点判断一下是否叶子节点,如果是则判断value之和是否与sum相同;如果不是叶子节点,就递归查找它的左右子节点。
python代码
|
|
Path Sum Ⅱ
进阶版Path Sum,不仅判断是否存在这样的路径,而是要求给出所有满足要求的路径。
原题地址
思路
总体思想与上一题类似,但是需要增加一个参数list来保存路径,所以需要重新写一个递归函数。注意往list里append值之后要对应的pop,否则后续对list的操作也会反映到最终结果上,因为最终返回的是一个List[List[int]],其中的每个list是浅拷贝。
python代码
|
|