题解 | #二叉树中和为某一值的路径(三)#

#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param sum int整型 
# @return int整型
#
# 本题不仅可以计算出符合要求的路径条数，还可以计算出符合要求的每条路径包含哪些节点
# 注意：本题目不要求从根节点开始到叶子界节点结束，即可以从任意节点开始到任意节点结束，而遍历二叉树的时候每走过一个节点就是一条新的路径
class Solution:
    def __init__(self):
        self.res = 0
        
    def FindPath(self , root: TreeNode, sum: int) -> int:
        # write code her 
        # 要计算符合要求的每条路径包含哪些节点要从本次遍历的起始节点开始记录，由于二叉树中可能包含值为0的节点，因此直到sum=0时也不能停止，继续遍历
        self.path = []  
        if not root:
            return 0
        def recur(pRoot, tar):
            if not pRoot:
                return None
            self.path.append(pRoot.val) # 每遍历一个节点就记录
            tar -= pRoot.val
            if tar == 0:
                self.res += 1
                for node in self.path:  # 当sum=0时打印一下本次路径
                    print(f"第{self.res}次:",node)
            recur(pRoot.left, tar)
            recur(pRoot.right, tar)
            self.path.pop()  # 这里是关键，每个节点的左右孩子节点都遍历完才弹出本节点
        
        recur(root, sum)
        self.FindPath(root.left, sum)
        self.FindPath(root.right, sum)
        return self.res