why the simple DFS recursion works?-CodePudding

For leetcode 112, the question asks you to find if there exists a path from root to leaf that their value add up to targetSum, the solution goes like this:

class Solution(object):
    def hasPathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: bool
        """
        
        if not root: return False
        
        if not root.left and not root.right:
            return root.val == targetSum
        
        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

And I can't wrap my head around why the last line inside the function breaks the recursion and returns the final True but if it's False it continues back to the DFS search.

CodePudding user response：

or short-circuits, so the return statement is just a short version of

t = self.hasPathSum(root.left, targetSum - root.val)
if t:
    return t
return self.hasPathSum(root.right, targetSum - root.val)

CodePudding user response：

but if it's False it continues back to the DFS search

This might be where you're getting lost. It doesn't really do two separate things: both options in the return statement execute a DFS. What this statement is saying is if you are at a leaf, which is written here:

if not root.left and not root.right:
        return root.val == targetSum

then if any path leads to the targetSum, return True, all other options return False. This is able to exit early if the answer is found when searching the left branch (as the code will return True there and never search the right branch) but the recursion always just ends at one of the two base cases:

if not root: return False

and

if not root.left and not root.right:
    return root.val == targetSum

CodePudding user response：

The recursion happen for both left and right side exhaustively (completely). Nothing breaks.

The final result is the OR operation of both left and right sides.

Edit: In python the second argument will be evaluated only if the first is false. (please check Gassa's comment)