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

 

 

---

Two Pointer 방식으로 해결하는 방법

Two Pointer 방식을 사용하려면, BST(Binary Search Tree)의 중위 순회(in-order traversal)를 수행하여 오름차순으로 정렬된 리스트를 만든 후, 투 포인터를 사용하여 두 숫자의 합이 k가 되는지 확인하면 된다.

Two Pointer 알고리즘

1. BST를 중위 순회하여 정렬된 리스트를 생성
   • 중위 순회(In-order Traversal)를 수행하면 BST의 값이 오름차순으로 정렬됨.
2. Two Pointer 기법을 활용하여 합이 k가 되는 두 수 찾기
   • 리스트의 left(처음)과 right(끝) 포인터를 설정.
   • 두 값의 합이 k보다 작으면 left를 증가.
   • 두 값의 합이 k보다 크면 right를 감소.
   • 두 값의 합이 k이면 True 반환.

# 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:
        nums = []  # 중위 순회 결과를 저장할 리스트

        # 중위 순회 함수 정의 (BST -> 정렬된 리스트 변환)
        def inorder(node):
            if not node:
                return
            inorder(node.left)  # 왼쪽 서브트리 탐색
            nums.append(node.val)  # 현재 노드 값 추가
            inorder(node.right)  # 오른쪽 서브트리 탐색

        inorder(root)  # 중위 순회 실행

        # Two Pointer를 사용하여 두 수의 합이 k가 되는지 확인
        left, right = 0, len(nums) - 1  # 왼쪽 포인터와 오른쪽 포인터 설정
        
        while left < right:
            two_sum = nums[left] + nums[right]  # 두 포인터의 합 계산
            
            if two_sum == k:  # 두 값의 합이 k라면 True 반환
                return True
            elif two_sum < k:  # 합이 k보다 작으면 왼쪽 포인터 이동 (더 큰 값 탐색)
                left += 1
            else:  # 합이 k보다 크면 오른쪽 포인터 이동 (더 작은 값 탐색)
                right -= 1

        return False  # 조건을 만족하는 두 수가 없으면 False 반환

 

---

연산	Time Complexity	Space Complexity
중위 순회 (In-order Traversal)	O(N)	O(N) (리스트 저장)
Two Pointer 탐색	O(N)	O(1) (추가 공간 없음)
총 복잡도	O(N)	O(N)

 

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