[LeetCode] 653. Two Sum IV - Input is a BST - 문제풀이

Description

주어진 유효한 이진검색트리에서 두개의 요소의 합이 k가 되는 경우가 있는지 여부를 반환하는 문제입니다.

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].
• -10^4 <= Node.val <= 10^4
• root is guaranteed to be a valid binary search tree.
• -10^5 <= k <= 10^5

Solution 1. DFS + HashTable

public boolean findTarget(TreeNode root, int k) {

    //1. Recursion - DFS
    Set<Integer> set = new HashSet<>();
    return dfs(root,set,k);
}

public boolean dfs(TreeNode node, Set<Integer> set, int k){
    if(node == null) return false;
    if(set.contains(k-node.val)){
        return true;
    }
    set.add(node.val);
    return dfs(node.left, set, k) || dfs(node.right, set, k);
}

깊이우선탐색(DFS)로 노드를 탐색해 나가면서 set를 이용한 hashTable에 (k-현재 노드의 값)이 있는지 확인 한 뒤 각 노드의 값을 hashtable에 저장해 줍니다.

node1+node2 = k

k-node1 = node2

Solution 2. BFS + HashTable

public boolean findTarget2(TreeNode root, int k) {

    //2. Iteration - BFS
    if(root == null) return false;
    Set<Integer> set = new HashSet<>();
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while(!q.isEmpty()){
        TreeNode cur = q.poll();
        if(set.contains(k-cur.val)){
            return true;
        }
        set.add(cur.val);
        if(cur.left != null)q.offer(cur.left);
        if(cur.right != null)q.offer(cur.right);
    }
    return false;
}

너비우선탐색(DFS)으로 큐를 이용하여 노드를 담아 탐색해 나가면서 set를 이용한 hashTable에 (k-현재 노드의 값)이 있는지 확인 한 뒤 다음 노드를 탐색하는 것을 반복하며 모든 노드를 탐색합니다.

Reference

Two Sum IV - Input is a BST - LeetCode