# 执行用时 :44 ms, 在所有 python3 提交中击败了99.18% 的用户

# 内存消耗 :14.2 MB, 在所有 python3 提交中击败了98.55%的用户

# Definition for a binary tree node.

class TreeNode:

    def __init__(self, x):

        self.val = x

        self.left = None

        self.right = None

from typing import List

class Solution:

    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:

        results = []

        res= []

        s = 0

        def recursion(root,s):

            # 如果遍历到一个分支的底了,则为空节点,返回True,继续遍历

            if root == None:

                return True

            res.append(root.val)

            # 注意不传s不行,全局变量s指向不可变对象,只能在里面调用,不能修改

            s = s + root.val

            a = recursion(root.left,s)

            b = recursion(root.right,s)

            # 如果到叶节点了,且和也满足条件,则存储

            if a and b:

                if s == sum:

                    results.append(res[:])

            s = s - root.val

            # 注意这里res是个全局变量,且因为指向可变对象所以可以修改,每次函数结束时,res中的

            # 内容不会自定返回到调用前的状态,所以需要出栈来恢复状态

            res.pop()

        recursion(root,s)

        return results

if __name__ == '__main__':

    duixiang = Solution()

    root = TreeNode(8)

    a = TreeNode(4)

    b = TreeNode(9)

    root.left = a

    root.right = b

    al = TreeNode(3)

    ar = TreeNode(6)

    a.left = al

    a.right = ar

    arl = TreeNode(5)

    arr = TreeNode(7)

    ar.left = arl

    ar.right = arr

    sum = 17

    a = duixiang.pathSum(root,sum)

    print(a)