题解 | #牛的奶量统计II#

• 题目考察的知识点 : 递归，深度优先遍历
• 题目解答方法的文字分析：

1. 基于 dfs 的递归特性,通过递归遍历和路径和计算,来实现寻找目标路径和
2. 定义当前路径和 curSum,通过递归累加 root.val,求出从根到当前节点的路径和。
3. 通过递归终止条件,如果路径和等于目标和,直接返回True。
4. 如果当前节点不是叶子,需要继续递归左右子节点。
5. 最终如果存在匹配的路径和,会通过递归返回True。
6. 通过不断递归,可以遍历树的所有路径,找出是否存在匹配的路径。

• 本题解析所用的编程语言：Python
• 完整且正确的编程代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param targetSum int整型 
# @return bool布尔型
#
class Solution:
    def hasPathSumII(self , root: TreeNode, targetSum: int) -> bool:
        if not root:
            return False
  
        return self.findPath(root, targetSum)

    def findPath(self, root, targetSum):
        if self.checkPath(root, 0, targetSum):
            return True

        if root.left:
            if self.findPath(root.left, targetSum):
                return True

        if root.right:  
            if self.findPath(root.right, targetSum):
                return True

        return False

    def checkPath(self, root, curSum, targetSum):
        curSum += root.val
        if curSum == targetSum:
            return True
  
        if curSum > targetSum:
            return False

        if root.left:
            if self.checkPath(root.left, curSum, targetSum):
                return True

        if root.right:
            if self.checkPath(root.right, curSum, targetSum):
                return True

        return False