leetcode:437. 路径总和 III【dfs 选还是不选？】

分析

思路很清晰
选不选当前的
选当前的带着和进入左右孩子
不选当前的直接进入左右孩子

选的话直接内层dfs搞定
不选的话外层调用self

得到一个以每个节点作为start
然后都选当前的一个判断

ac code

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def dfs(root, targetSum):
            if not root:
                return 0
            
            ret = 0 
            if root.val == targetSum:
                ret += 1
            # 选了当前root的
            ret += dfs(root.left, targetSum - root.val)
            ret += dfs(root.right, targetSum - root.val)

            return ret
        
        if not root:
            return 0

        ret = dfs(root, targetSum)
        # 不选当前root
        ret += self.pathSum(root.left, targetSum)
        ret += self.pathSum(root.right, targetSum)
        return ret

总结

选当前的就进入dfs，然后判断none，如果刚好等就+1
否则选了当前进入下一层dfs

若不选当前直接在外面进入pathSum，无视掉root.val的值即可

这里就是一个经典的 选当前再遍历左右 or 不选当前就遍历左后