[재귀 + DFS] LeetCode 112번 문제 학습

 

문제에 대한 설명

1. 이 문제는 이진 트리에서 루트부터 리프까지의 경로 합이 targetSum과 같은지 확인하는 문제임.
2. 경로가 리프에서 끝나야 하고, 그 합이 targetSum과 일치해야 함.
3. 한 경로라도 조건을 만족하면 true를 반환하면 됨.

문제를 푼 과정

1. DFS로 경로 합을 계산하려고 재귀 함수를 작성했음.
2. 리프 노드에서 합을 체크하려 했지만 로직이 맞지 않았음.
3. 에러가 발생한 건 널 포인터 참조와 합 계산 방식 때문임.

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}

func dfs(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}

	if root.Left == nil && root.Right == nil {
		return false
	}

	val_left := targetSum + root.Left.Val
	val_right := targetSum + root.Right.Val

	if val_left == targetSum || val_right == targetSum {
		return true
	}


	left := dfs(root.Left, targetSum + root.Left.Val)
	right := dfs(root.Right, targetSum + root.Right.Val)

	if left || right {
		return true
	}

	return false
}

func hasPathSum(root *TreeNode, targetSum int) bool {
	return dfs(root, targetSum)
}

에러 원인

1. 널 포인터 참조:
   • val_left := targetSum + root.Left.Val와 val_right := targetSum + root.Right.Val에서 root.Left나 root.Right가 nil일 때 .Val을 참조하면 런타임 에러(panic) 발생.
   • 예: root_3에서 오른쪽이 nil인데 root.Right.Val을 호출함.
2. 로직 오류:
   • 리프 노드에서 return false로 해버려서 합이 targetSum과 같은지 체크 못 함.
   • 합을 누적하는 방식이 잘못됨. targetSum에 더하는 대신, targetSum에서 빼면서 내려가야 함.
   • 중간에 val_left == targetSum 같은 조건은 의미 없음 (리프에서만 확인해야 함).

수정 방향

• dfs에서:
  • nil 체크를 먼저 하고, 리프에서만 합을 확인.
  • targetSum에서 현재 값을 빼면서 재귀 호출.
• 리프 조건에서 남은 targetSum이 노드 값과 같은지 확인.

---

문제를 풀려면 어떤 알고리즘을 써야 하는지

1. 재귀를 사용해서 경로를 탐색해야 함.
2. DFS를 통해 리프까지의 합을 계산하면 됨.
3. 각 노드에서 합을 누적하며 리프에서 확인하는 방식이 적합함.

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func dfs(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}

	if root.Left == nil && root.Right == nil {
		return targetSum == root.Val
	}

	if root.Left != nil {
		if dfs(root.Left, targetSum - root.Val) {
			return true
		}
	}

	if root.Right != nil {
		if dfs(root.Right, targetSum - root.Val) {
			return true
		}
	}

	return false
}

func hasPathSum(root *TreeNode, targetSum int) bool {
	return dfs(root, targetSum)
}

동작 확인

• root_1, 22: 5->4->11->2 (5+4+11+2=22) → true.
• root_2, 3: 1->2 (1+2=3) → true.
• root_3, 1: 1->2 (1+2=3≠1) → false.
• root_4, 5: 1->2 (3), 1->3 (4) 모두 5 아님 → false.