LeetCode 112(Path Sum, java)

0. 문제

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

Path Sum - LeetCode

 

1. 문제 설명

- 문제에서 이진트리(root)와 정수(targetSum)가 주어진다.

- 루트 노드를 시작으로 단말 노드까지의 value를 합하여 targetSum을 만들 수 있는지 확인하는 것이 문제의 핵심이다.

 

2. 문제 해설

a) 첫 번째 접근

- 우선 true를 반환하는 경우를 생각해보자.

- 가장 먼저 생각할 수 있는 조건은 targetSum == 0 이어야 한다는 것이다.

 

- 단말 노드까지 탐색해야 하므로 targetSum이 0일 때, root.left와 root.right가 null이어야 한다.

- 이것이 첫 번째 조건이다. 

 

b) 두 번째 접근

- 그렇다면 false가 발생할 조건은 무엇일까?

- 우선 true 조건에서 targetSum이 0일 때를 언급했다. 

- 그러므로 false 조건은 단말 노드까지 도달했을 때가 된다. 

- 즉, root == null인 경우다. 

 

c) 세 번째 접근

- 이제 어떻게 반복할지 생각해보자.

- 이진 트리를 탐색할 때에는 대부분 재귀 함수를 사용한다. 

- 그 이유는 반복문으로 탐색할 때 종료 시점이 명확하지 않기 때문이다. 

- while문을 사용하여 root가 null인 경우 종료하면 되지 않냐고 생각할 수 있으나, 이진트리에서 단말 노드는 하나가 아니다.

- 그러므로 재귀 함수를 사용하여 이진 트리를 탐색한다.

 

d) 네 번째 접근

- 그렇다면 재귀를 어떻게 호출해야할까?

- 이진트리의 부모 노드는 최대 2개의 자식 노드를 가질 수 있다. 

- 즉, 좌측으로 탐색하거나 우측으로 탐색하는 경우를 생각해야 한다.

 

- 위에서 생각한 조건들을 다음 코드로 적용할 수 있다.

- 코드를 보면서 이해해보자.  

 

3. 정답 코드

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        
        if(root == null) {
            return false;
        }
        
        if(targetSum - root.val == 0 && root.left == null && root.right == null) {
            return true;
        }
        
        return (hasPathSum(root.left, targetSum - root.val)) || 
                 (hasPathSum(root.right, targetSum - root.val));
    }
}