[leetcode #653] Two Sum IV - Input is a BST

Problem

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

Example 3:

Input: root = [2,1,3], k = 4
Output: true

Example 4:

Input: root = [2,1,3], k = 1
Output: false

Example 5:

Input: root = [2,1,3], k = 3
Output: true

Constraints:

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

Idea

주말에 부산에 일이 있어 다녀왔더니 leetcode 풀 생각도 못 했다. 다 난이도가 어렵길래 우선 오늘 것부터 풀고 나머지는 나중에 풀어보는 걸로...

오늘 문제는 tree에서 두 노드의 합이 k값이 되는 노드들이 있는지 찾는 문제다. 난이도는 당연히 쉬울 거라 생각하고 자신감있게 풀었다.

우선 Set을 준비한다. Set을 사용하는 이유는 노드를 탐색하면서 쌍이 되는 값이 있는지 찾기 위함이다. 예를 들어 현재 노드가 2고 k가 3이라면 1이 set에 있는지 확인하면 된다. set에 원하는 값이 없을 경우 (k - 현재 값)을 set에 넣는다. k가 되는 쌍이 발견되면 탐색을 멈추고 true를 리턴한다. 트리 탐색이 끝난 뒤에도 합이 k가 되는 노드 쌍이 없으면 false를 리턴한다.

알고리즘

1. Set을 만든다.
2. 트리를 탐색한다.
   a. 노드가 null일 경우 false를 리턴한다
   b. 노드값이 set에 있을 경우 true를 리턴한다.
   c. 노드값이 set에 없을 경우 (k - node.val)을 set에 넣어준다.
3. 탐색한 결과를 리턴한다.

Solution

class Solution {
    Set<Integer> set;

    public boolean findTarget(TreeNode root, int k) {
        set = new HashSet<Integer>();

        return traverseTree(root, k);
    }

    private boolean traverseTree(TreeNode node, int k) {
        if (node == null)
            return false;

	if (set.contains(node.val))
	    return true;

	set.add(k - node.val);

	return traverseTree(node.left, k) || traverseTree(node.right, k); 
    }
}

Reference

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