LeetCode 653(Two Sum IV - Input is a BST, java)

0. 문제

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

Two Sum IV - Input is a BST - LeetCode

 

1. 문제 설명

- 문제에서 이진 탐색 트리(root)와 찾는 수(k)가 주어진다.

- 트리를 구성하는 노드 중 2개 노드의 value 합이 찾는 수인 경우가 존재하는지 판단하는 것이 문제의 핵심이다.

2. 문제 해설

a) 첫 번째 접근

- 우선 모든 노드를 탐색하여 노드가 가진 value를 자료구조에 저장하는 것이 첫 번째 단계다.

- 그렇다면 어떤 자료구조를 사용해야 할까? 

- 이진 탐색 트리의 경우, 동일한 value를 가진 노드가 존재하지 않으므로 Set을 이용할 수 있다.

 

b) 두 번째 접근

- 이제 어떤 방식으로 노드의 합을 계산할지 생각해보자. 

- 이진 탐색 트리를 탐색하면서 Set에 들어있는 노드를 검증한다.

 

- 만약 (k - value)의 값이 Set에 존재한다면 true를 반환한다. 

- 존재하지 않는 경우, 해당 노드의 value를 Set에 저장한 후 계속해서 탐색을 이어나간다.

- 만약 모든 노드를 탐색했는데도 k를 만들 수 있는 짝을 발견하지 못했다면 false를 반환한다. 

 

- 이 과정을 재귀로 구현하면 끝이다.

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

 

3. 정답 코드

class Solution {
    
    Set<Integer> set = new HashSet<>();
    
    public boolean findTarget(TreeNode root, int k) {
        if(root == null) {
            return false;
        }
        
        if(set.contains(k - root.val)) {
            return true;
        }
        else {
            set.add(root.val);
        }
        return findTarget(root.left, k) || findTarget(root.right, k);
    }
}