Leetcode # 112. Path Sum

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

Solution

Return True if the tree has a root-to-leaf path

Time Complexity: O(len(tree))
Space Complexity: O(len(tree))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
    stack = [[root, 0]] if root else []
    while stack:
      cur, sum = stack.pop()
      sum += cur.val
      # Return True if the tree has a root-to-leaf path.
      if not cur.left and not cur.right and sum == targetSum: return True
      for child in [cur.left, cur.right]:
        if child:
          stack.append([child, sum])
    return False

Last Updated on 2023/08/16 by A1go