Leetcode 1214. Two Sum BSTs

문제

Given the roots of two binary search trees, root1 and root2, return true if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

• 주어진 2개의 이진탐색 트리에 대해 두 트리의 노드값중 각 하나를 뽑았을때 그 합이 target이 될수 있으면 True를 리턴하시오

예시

• 왼쪽 트리에서 2, 오른쪽 트리에서 3 가져오면 2 + 3 == 5이기에 true

제한

• 트리의 노드 갯수는 1 이상 5000 이하.
• $-10^9 <= Node.val, target <= 10^9$

풀이

# 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 twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:

        def transform(node: Optional[TreeNode], arr: List[int]):
            if node:
                transform(node.left, arr)
                arr.append(node.val)
                transform(node.right, arr)

        a, b = [], []

        transform(root1, a)
        transform(root2, b)

        left = 0
        right = len(b) - 1

        while left < len(a) and right >= 0:
            if a[left] + b[right] < target:
                left += 1
            elif a[left] + b[right] > target:
                right -= 1
            else:
                return True

        return False

해당 문제는 순서대로 작은 태스크를 해결하면 된다.

1. in-order 순회를 통해 BST를 평탄화 한다.
   • 여기서 BST를 중위순회 할 경우 반드시 오름차순 정렬되는점을 이용한다.
2. two-pointer로 가능한 합이 있는지 찾는다.