leetcode:437. Path sum III [DFS selected or not selected?]

analysis

Clear thinking
Select or not select the current
Choose the current one, take and enter the left and right children
Don't choose the current one and go directly to the left and right children

If you choose, go directly to the inner layer dfs Get it done
If not selected, the outer layer calls self

Get one with each node as start
Then choose the current judgment

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
            #  Current selected root Of 
            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)
        #  Not the current root
        ret += self.pathSum(root.left, targetSum)
        ret += self.pathSum(root.right, targetSum)
        return ret

summary

Select the current to enter dfs, And then determine none, If you just wait +1
Otherwise, select the current to enter the next layer dfs

If you don't choose to enter directly from the outside pathSum, Ignore root.val The value of the can

Here is a classic Select the current and then traverse the left and right or If you don't select the current, you can traverse the left back