[LeetCode] 653. Two Sum IV - Input is a BST

653. Two Sum IV - Input is a BST

Easy

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, 104].
• -104 <= Node.val <= 104
• root is guaranteed to be a valid binary search tree.
• -105 <= k <= 105

---

문제 풀이

• 바이너리 트리가 주어지고, 두 숫자의 값이 k 가 같은지 확인하는 문제이다.
• 재귀 함수를 이용하여 트리를 순회한다. 
• 해쉬테이블을 만들고, k 에서 현재 노드 값을 뺀 것을 해쉬 테이블에 저장하면서 탐색한다.
• 현재 값이 해쉬 테이블에 있다면 정답처리한다. 
• 이전에 목표값에서 숫자를 뺀 값을 미리 저장하고 있기 때문에 가능하다.

코드 소드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        hash_table = dict()
        self.ans = False
        def bs(node):
            if not node:
                return
            
            if node.val in hash_table:
                self.ans = True
                return
            hash_table[k - node.val] = 1
            
            bs(node.left)
            bs(node.right)
        bs(root)
        return self.ans