113、Path Sum2

与上一题的不同，不同之处需要改变的地方，因为改变而需要注意的地方。

与上一题不同之处

这一题相对于112题，题目增加了一个要求：将满足条件的路径都输出。

因此需要改变的地方

那么我们就要构造一个结果列表res_list，里面的元素为代表正确路径的节点值得列表。

结合具体的例子，我们发现，想要记录路径，就要用一个栈，对于访问过的点，若不是正确路径就弹出。因此再用一个in_list来模拟栈操作。

因为改变，而需要注意的地方

注意1：再定义一个递归函数

因为要定义两个列表，又不能在递归函数里定义。所以，为此需要构造一个新的函数helper用来递归，在递归函数外面定义变量。
当递归函数需要新的变量时，一般都会在函数里再定义一个递归函数。

注意2：递归函数不是同时进行的

递归函数不是同时进行调用的，而是一个一个的调用到底，再按照栈的思想返回到最近的上一个递归函数的。所以，对in_list的操作也只会一步一步的进行，不会同时进行。不需要顾虑in_list会乱。

注意3：要清楚in_list在每一步的状态

递归函数的最后，一定要弹出这个点。
比如[5,4,11,2]的结果，在第一二三次调用时，每个递归函数都没有结束
第四次递归函数结束时，此时需要执行一下pop，弹出2这个点，然后return，返回上一个递归函数。继续执行。

那么在上一个递归中，11的左子节点递归步骤结束，会继续执行11的右子节点的递归函数。

此时，传入的右子节点的list，就是[5,4,11]，可以再次压入11的右子节点。

注意4：Python的一个坑！

因为这里是用list来模拟栈，因此，
若是采用res_list.append(in_list)的语句，那么append的元素是对in_list的引用，而in_list是不断在变化的。那么在最终返回res_list时，返回的对in_list的引用。那么得到的就是最后的in_list的结果“[ ]”。（最终得到的所有的路径就都是空集）。
比如，这里最后得到的res_list的输出会是 [ [ ],[ ] ]。

L = []
in_L = [1, 2, 3]
L.append(in_L[:])
in_L.pop()
print(L)

上面代码中，最终输出的会是[1,2]！

要想复制一个list，并且这个list是在变化的，就要用切片。

因此用一个切片，来append一个不会变的结果：
res_list.append(in_list[:])

递归函数的分析：

递归结束条件：

1、若节点为空，直接返回，不需要压入弹出栈操作
2、若不为空，那么就要压入此点，接着判断：
若是叶节点并且正确路径，就把list添加到res_list中，再return，跳出这个递归函数
3、（若是叶节点，不是正确路径，就直接return，这个由上面一题中第三条递归结束条件
一样，由两个递归函数也可代替，然后执行完两个递归函数以后，也能直接从出口出来）

递归改变条件：

list每次都在改变，节点每次都在访问

递归调用：

root的左右子节点分别调用递归函数

代码实现：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """

        res_list = []
        in_list = []
        def PathSumHelper(root,sum,in_list):
            if root == None:
                return
            #若是不等于None，就压入这个节点
            in_list.append(root.val)
            if root.left == None and root.right == None and root.val == sum:
                res_list.append(in_list[:])
            #在判断完这个节点之后，要删除这个节点，这样下一次递归时，list就是没用过的了
            PathSumHelper(root.left,sum-root.val,in_list)
            PathSumHelper(root.right,sum-root.val,in_list)
            in_list.pop()
            return
        PathSumHelper(root,sum,in_list)
        return res_list