前言
新的一年，好好学习。尝试用python写写代码。
正文
问题来源
本问题来自leetcode上的113题。
问题描述
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例 1:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回
[
[5,4,11,2],
[5,8,4,5]
]
分析：
回溯法 用一个path记录走过的路径，当回溯到上一层时，退回路径。当路径和与目标值相同时，拷贝一份path，加入到结果集中。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def __init__(self):
self.path = []
self.ret = []
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
if not root:
return []
self.paths(root, sum)
return self.ret
def paths(self, root, sum):
self.path.append(root.val)
if not root.left and not root.right:
if sum == root.val:
self.ret.append(list(self.path))
self.path.pop()
return
if root.left:
self.paths(root.left, sum-root.val)
if root.right:
self.paths(root.right, sum-root.val)
self.path.pop()
递归版（别人）
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
result = []
self.help(root, sum, [], result)
return result
def help(self, root, sum, path, result):
if root is None:
return
path.append(root.val)
if root.left is None and root.right is None:
if sum == root.val:
result.append(list(path))
self.help(root.left, sum - root.val, path, result)
self.help(root.right, sum - root.val, path, result)
path.pop()
跟leetcode 112一样
将左右子树作为参数传入递归调用前，不进行判None，效率比判断None快，这个是我没有想到的。
总结：
勤思考。
我第一反应list的list要写成[[]]，所以不能理解成为list的list这样，就是个list，里面可以装任何类型，这样才对吧？
list类型的append是将引用加入list中，而不会进行内容的浅拷贝（Java，Go都是这样做的）。这个和C++中vector的push_back不同。
python返回多值，譬如我返回 A、B，但是我只想要B，不想要A的话，可以_, b = fun()这样写
结语
不管怎么样好好加油。
