[Leetcode][python3] 112. Path Sum

problem: https://leetcode.com/problems/path-sum/

 

code :

dfs

recursive

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        
        # recursive
        def _dfs(cur, curSum):
            
            # exit condition
            if cur == None :
                return False
            
            # optimizing
            #if curSum > targetSum or cur.val+ curSum > targetSum:
            #    return False
            
            # exit condition
            if cur.left==None and cur.right==None : 
                if curSum + cur.val == targetSum :
                    return True
                else :
                    return False
            
            return (_dfs(cur.left, curSum+cur.val) or _dfs(cur.right, curSum+cur.val))
                
            
        return _dfs(root, 0)

 

 

# 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

# q : 4 13 
# cur : 1
# curSum : 18

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        
        # stack - DFS
        q = []
        q.append((root, 0))
        while q:
            cur, curSum = q.pop(-1)
            if cur==None :
                return False
            curSum += cur.val
            if cur.left== None and cur.right== None :
                if curSum == targetSum:
                    return True                 
            
            if cur.left:
                q.append((cur.left, curSum))
            if cur.right:
                q.append((cur.right, curSum))
                
        return False