[Leetcode/Hash Set] 653. Two Sum IV - Input is a BST

해시셋(Hash Set) 활용 -
중복을 방지하면서 각 노드를 탐색할 때 (k - 현재 노드 값)이 존재하는지 확인하는 방법.

 

설명

• dfs 함수를 사용하여 트리를 깊이 우선 탐색(DFS) 한다.
• 각 노드를 방문할 때 k - node.val이 seen 집합에 존재하는지 확인한다.
• 존재하면 True를 반환하고, 없으면 현재 노드 값을 seen에 추가한 후 왼쪽과 오른쪽 서브트리를 탐색한다.
• 전체 탐색이 끝날 때까지 조건을 만족하는 쌍이 없으면 False를 반환한다.

시간 복잡도

• 각 노드를 한 번씩 방문하므로 O(N) (N은 트리의 노드 개수).

공간 복잡도

• 최악의 경우 모든 노드 값을 seen에 저장해야 하므로 O(N).

 

# 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:
        seen = set()  # 이미 방문한 노드 값을 저장하는 집합(Set)

        # 깊이 우선 탐색 (DFS) 함수 정의
        def dfs(node):
            if not node:  # 현재 노드가 None이면 종료 (기저 사례)
                return False
            
            # (k - 현재 노드 값)이 seen 집합에 있다면, 두 숫자의 합이 k가 되는 쌍이 존재함을 의미
            if (k - node.val) in seen:
                return True  # 조건 만족 → True 반환
            
            # 현재 노드 값을 집합에 추가 (나중에 방문할 노드들과 비교할 수 있도록)
            seen.add(node.val)

            # 왼쪽 서브트리 또는 오른쪽 서브트리에서 조건을 만족하는 경우가 있는지 확인
            return dfs(node.left) or dfs(node.right)

        # DFS 탐색 시작 (루트 노드부터)
        return dfs(root)

코드 설명

1. seen 집합(Set)을 사용하여 방문한 노드 값을 저장
   • 중복 방문을 방지하고, 현재 노드에서 k - node.val이 존재하는지 빠르게 확인할 수 있도록 함.
2. DFS(깊이 우선 탐색) 방식으로 트리 탐색
   • if not node: → None이면 탐색 종료.
   • (k - node.val) in seen → 현재 노드의 보수(k - node.val)가 이미 seen에 존재하는 경우 True 반환.
   • seen.add(node.val) → 현재 노드 값을 저장하여 이후 방문하는 노드와 비교할 수 있도록 함.
   • return dfs(node.left) or dfs(node.right) → 왼쪽 또는 오른쪽 자식 노드에서 조건을 만족하면 True 반환.

시간/공간 복잡도

• 시간 복잡도: O(N) (모든 노드를 한 번씩 방문)
• 공간 복잡도: O(N) (최악의 경우 모든 노드 값을 seen에 저장)

 

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