653. Two Sum IV - Input is a BST

653. Two Sum IV - Input is a BST

 

이 문제 LeetCode 653. Two Sum IV – Input is a BST는
BST에서 두 노드의 값을 더해서 k가 되는 경우가 있는지 확인하는 문제입니다.
기본적으로 Two Sum + BST 탐색의 조합이에요.

---

✅ 핵심 아이디어

BST를 순회하면서,

• 각 노드 val에 대해 k - val이 다른 노드에 존재하는지를 확인합니다.
• 이를 위해 set을 활용하거나, inorder + two pointer 방식으로 접근할 수 있어요.

---

✅ 방법 1: DFS + HashSet (빠르고 직관적인 방법)

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        seen = set()  # 지금까지 탐색한 노드의 값들을 저장하는 집합

        def dfs(node):
            if not node:
                return False  # 리프 노드 넘어서면 False 반환

            # 현재 노드의 값이 val 이라면, k - val 을 이전에 본 적이 있는지 확인
            if (k - node.val) in seen:
                return True  # 두 수의 합이 k인 경우를 찾음

            # 현재 노드 값 저장
            seen.add(node.val)

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

        return dfs(root)  # 루트부터 DFS 시작

---

📘 동작 방식

• 노드를 하나씩 순회하며, k - node.val이 seen에 있으면 바로 True 반환
• 없으면 node.val을 seen에 저장하고 왼쪽/오른쪽 자식으로 계속 진행

---

✅ 방법 2: Inorder Traversal + Two Pointer (BST 구조 활용)

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        nums = []  # inorder 순회를 통해 노드를 오름차순 배열로 저장할 리스트

        def inorder(node):
            if not node:
                return  # None이면 종료
            inorder(node.left)      # 왼쪽 서브트리 순회
            nums.append(node.val)   # 현재 노드 값 저장
            inorder(node.right)     # 오른쪽 서브트리 순회

        inorder(root)  # BST를 inorder 방식으로 순회 → nums는 오름차순 정렬됨

        # 이제 nums 배열에서 two pointer로 두 수의 합이 k가 되는 쌍을 찾기
        l, r = 0, len(nums) - 1  # 왼쪽 포인터, 오른쪽 포인터

        while l < r:
            total = nums[l] + nums[r]

            if total == k:
                return True  # 두 수의 합이 k면 True
            elif total < k:
                l += 1  # 합이 작으면 왼쪽 포인터를 오른쪽으로 이동
            else:
                r -= 1  # 합이 크면 오른쪽 포인터를 왼쪽으로 이동

        return False  # 끝까지 탐색했는데 못 찾으면 False

---

🆚 비교 요약

방식	장점	단점
DFS + HashSet	구현 간단, 빠름	중복 체크 주의 필요
Inorder + Two Pointer	BST 구조를 최대한 활용	배열 저장 공간 추가 필요

🔄 두 방식 요약 정리

방식	탐색	공간	특징
DFS + HashSet	O(n)	O(n)	빠르고 코드 짧음, 중복 체크 간단
Inorder + Two Pointer	O(n) + O(n)	O(n)	BST 오름차순 속성 이용, 정렬 배열 기반

---

✅ 결론

• 둘 다 인터뷰에서 좋아하는 방식이고, 상황에 따라 선택 가능!
• 빠르고 간단한 구현 원하면 DFS + HashSet
• BST 구조를 깊게 활용하고 싶으면 Inorder + Two Pointer

 

---

---

내 코드

# 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:
        visit = set()

        def dfs(node):
            if not node: # 마지막까지 오면 없는것임
                return False

            # (k-node.val) + node.val 은 k 를 만족하니, 
            # (k-node.val) 가 이미 visit 에 있으면, 만족하는 값 찾은것임
            if k-node.val in visit: 
                return True

            # 현재 값 추가하고
            visit.add(node.val)

            # 현재 노드기준에서, 왼쪽이든, 오른쪽이든 참있으면 참임
            # 그래서, or 로 하면 됨
            return dfs(node.left) or dfs(node.right)
        
        return dfs(root)