Backtracking: 112. Path Sum ★★

112. Path Sum

 

# 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:
        # DFS로..
        def dfs(node, curSum):
            if not node:
                return False

            curSum += node.val
            # not node.left and not node.right: 왼쪽, 오른쪽 둘다 없으면: 리프 노드임
            
            if not node.left and not node.right:
                # 리프 노드에서 현재까지의 curSum 이 targetSum 와 같으면 True
                return curSum == targetSum

            return (dfs(node.left, curSum) or 
                    dfs(node.right, curSum))

        return dfs(root, 0)

 

 

https://youtu.be/LSKQyOz_P8I?si=C5_7xA-Yqq7ZBMfV

 

이제 풀림

 

# 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:
        # root에서 leaf 까지 sum 중 targetSum 이 있으면 True, 아니면, false

        def dfs(node, pathsum):
            if not node: # 없으면
                return False
            
            if not node.left and not node.right and ((pathsum + node.val) == targetSum): # 리프노드면
                return True

            if dfs(node.left, pathsum + node.val): # true 면
                return True
            
            if dfs(node.right, pathsum + node.val): # true 면
                return True

            return False

        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
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        root2leaf = []

        def backtrak(node, path, curr_sum):
            # 노드가 없으면
            if not node:
                return None
            
            # preorder: 현, 왼, 오
            path.append(node.val)
            curr_sum += node.val

            # 리프노드이면
            if not node.left and not node.right:
                if curr_sum == targetSum:
                    root2leaf.append(path[::]) # 깊은 복사로 저장
                
            # 리프노드 아니면
            backtrak(node.left, path, curr_sum)
            backtrak(node.right, path, curr_sum)
            path.pop() # 백트래킹

        backtrak(root, [], 0)
        # print(root2leaf)
        return len(root2leaf) > 0

 

최종 코드

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:

        # 현재 노드와 지금까지의 누적 합을 받아서 처리하는 DFS 함수
        def dfs(node, current_sum):
            # 노드가 None이면, 더 이상 탐색할 경로가 없으므로 False 반환
            if not node:
                return False

            # 현재 노드의 값을 누적 합에 더함
            current_sum += node.val

            # 현재 노드가 리프 노드인 경우 (왼쪽과 오른쪽 자식이 모두 없음)
            if not node.left and not node.right:
                # 지금까지의 누적 합이 targetSum과 같으면 정답이므로 True 반환
                return current_sum == targetSum

            # 왼쪽 또는 오른쪽 자식 노드로 DFS 계속 진행
            # 둘 중 하나라도 조건을 만족하면 True가 반환됨
            return dfs(node.left, current_sum) or dfs(node.right, current_sum)

        # 루트 노드에서부터 DFS 시작, 초기 누적 합은 0
        return dfs(root, 0)

 

✅ 정리부터 할게요:

조건	의미
if not node	노드 자체가 없음 → None인 경우
if not node.left and not node.right	리프 노드 (현재 노드는 존재하지만, 자식이 없음)

---

🔍 리프 노드 vs None 차이

예를 들어, 이런 트리를 보세요:

    5
   /
  4
 /
11
/
7

• 노드 7은 리프 노드입니다.
  👉 node는 TreeNode(7)이고, node.left == None, node.right == None
  👉 이 경우:

if not node:           # ❌ False (노드는 있음)
if not node.left and not node.right:  # ✅ True (자식이 없음 → 리프 노드)

• 반면, node.left 또는 node.right가 None이면:
  • 👉 아예 자식 노드가 없다는 뜻이에요 → dfs(None)으로 호출되면 not node == True

---

🧠 결론

코드	의미	예시
if not node	노드 자체 없음 (None)	dfs(node.left)에서 node.left == None일 때
if not node.left and not node.right	리프 노드 판별	현재 노드가 7일 때 (자식 없음)

---

그래서 dfs(node)에서

if not node:
    return False  # 트리 없음

if not node.left and not node.right:
    return current_sum == targetSum  # 리프 노드에서 체크

이렇게 분리해서 조건을 검사해야 정확한 로직이 됩니다.