112. Path Sum

Description

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

• Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
• Output: true
• Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

• Input: root = [1,2,3], targetSum = 5
• Output: false
• Explanation: There are two root-to-leaf paths in the tree:
  (1 –> 2): The sum is 3.
  (1 –> 3): The sum is 4.
  There is no root-to-leaf path with sum = 5.

Example 3:

• Input: root = [], targetSum = 0
• Output: false
• Explanation: Since the tree is empty, there are no root-to-leaf paths.

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

Submitted Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def hasPathSum(self, root, targetSum):
        """
        :type root: Optional[TreeNode]
        :type targetSum: int
        :rtype: bool
        """
        if not root:
            return False

        sum = 0
        stack = [(0, root)]

        while stack:
            sum, node = stack.pop()
            sum += node.val

            if not node.left and not node.right:    # 잎 노드에 도달
                if sum == targetSum:
                    return True

            if node.right:                          # 오른쪽, 왼쪽 순으로 스택에 추가
                stack.append((sum, node.right))
            if node.left:
                stack.append((sum, node.left))

        return False

Runtime: 0 ms | Beats 100.00%
Memory: 14.32 MB | Beats 25.81%

스택을 사용해서 실행 시간을 단축해봤다.

class Solution(object):
    def hasPathSum(self, root, targetSum):
        if not root:
            return False

        def count_sum(root, targetSum, sum):
            if not root.left and not root.right:
                return False if sum + root.val != targetSum else True
            else:
                l_tree = False if not root.left else count_sum(root.left, targetSum, sum+root.val)
                r_tree = False if not root.right else count_sum(root.right, targetSum, sum+root.val)

            if l_tree or r_tree:
                return True
            else:
                return False
        
        return count_sum(root, targetSum, 0)

재귀 호출을 이용한 방법은 거의 꼴지에 가까운 실행시간을 기록했다. 또 깊이 우선 탐색의 문제점을 알게 됐다.
왼쪽 서브트리나 오른쪽 서브트리의 결과 중 하나가 True이면 or 이기 때문에 True를 반환하는데, 파이썬에서는 더 앞에 위치하는 l_tree에서 True가 나올 경우 자동으로 뒤의 r_tree의 계산을 스킵하는 것 같다. 하지만 r_tree가 True여도 l_tree 계산은 무조건 하게 되기 때문에 어느 쪽 잎 노드가 정답인지에 따라 효율이 많이 달라질 수 있다.

Other Solutions

1st

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        
        if not root.left and not root.right:
            return targetSum == root.val
        
        left_sum = self.hasPathSum(root.left, targetSum - root.val)
        right_sum = self.hasPathSum(root.right, targetSum - root.val)
        
        return left_sum or right_sum

time complexity: 𝑂(𝑛)
space complexity: 𝑂(ℎ)

따로 합을 계산하는 변수를 만들지 않고 targetSum에서 빼는 방식으로 공간을 절약한 예시였다.

2nd

from collections import deque

class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if not root:
            return False
        
        queue = deque([(root, targetSum - root.val)])
        
        while queue:
            node, curr_sum = queue.popleft()
            
            # Check if the current node is a leaf and its sum is zero
            if not node.left and not node.right and curr_sum == 0:
                return True
            
            # Add left child to queue if exists
            if node.left:
                queue.append((node.left, curr_sum - node.left.val))
            
            # Add right child to queue if exists
            if node.right:
                queue.append((node.right, curr_sum - node.right.val))
        
        return False

큐를 사용하여 너비 우선 탐색을 하면 좌우 상관없이 균일한 실행시간을 가질 수 있다.

root = [5,4,8,11,null,13,4,7,2,null,null,null,1]
targetSum = 22

     [5]
     / \
   [4]  8
   /   / \
 [11] 13  4
 /  \      \
7   [2]     1
queue                         node.val     curr_sum	
[(5, 22)]                      5           17 (22 - 5)
[(4, 17), (8, 17)]             4           13 (17 - 4)
[(8, 17), (11, 13)]           11            2 (13 - 11)
[(8, 17), (7, 2), (2, 2)]      2            0 (2 - 2) → True

return True