[leetcode] 112. Path Sum

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

 

 

재귀 함수를 사용하여 깊이 우선 탐색(DFS)를 진행한다.

순회중에 leaf node 를 만났을 때, targetSum 조건에 만족하는지 확인한다.

sum=0 을 설정해두고, val 을 더해가면서 targetSum 까지 도달하는지 확인해도 좋다.

반대로 targetSum 에서 val 을 빼가면서 targetSum 이 0까지 도달하는지 확인해도 좋다.

 

 

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

 

 

 

---

 

 

 

< English (feedback by ChatGPT) >

 

 

Do Depth-First Search using a recursive function.

(Perform a Depth-First Search (DFS) using a recursive function.)

 

When we encounter leaf nodes in traversing, check whether the targetSum condition is fullfil.

(When you encounter a leaf node during traversal, check whether it satisfies the targetSum condition.)

 

After assing sum=0, It's good to check if sum adding with val equals to targetSum.

(One approach is to start with sum = 0 and add each node’s value to see if the total reaches targetSum.)

 

Alternatively, It's also good to check if targetSum subtracting val equals to 0.

(Alternatively, you can subtract each node’s value from targetSum and check if it reaches 0.)