[Leetcode] Easy: 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

Example 2:

Input: root = [1,2,3], targetSum = 5 Output: false

Example 3:

Input: root = [1,2], targetSum = 0 Output: false

 

My solution

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        visited = []
        results = []
        def dfs(self, node):
            if (not node.left) and (not node.right):
                results.append(node.val)

            if node not in visited:
                visited.append(node)
                if node.left:
                    node.left.val += node.val
                    dfs(self, node.left)
                if node.right:
                    node.right.val += node.val
                    dfs(self, node.right)
        if not root:
            return False
        else:        
            dfs(self, root)
            return targetSum in results

저는 search한 결과를 한 리스트에 저장하여 targetSum이 있다면 True, 없으면 False를 return하는 방식으로 구현하였습니다. 하지만 이는 어제 풀었던 [프로그래머스] 타겟 넘버처럼 recursive한 방식으로도 풀 수 있는 것을 확인할 수 있었습니다. 

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

 

문제 출처 : https://leetcode.com/problems/path-sum/submissions/

Path Sum - LeetCode