[LeetCode] 1214. Two Sum BSTs

 inorder를 통해 BST를 traverse하면서 list에 오름차순으로 값을 넣고, 첫번째 list는 작은 숫자부터, 두번째 list는 큰 숫자부터 더하는 Two Pointer 방식으로 target을 찾았고 없으면 False를 반환한다.

class Solution:
    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
        def inorder(n):
            if n == None:
                return []
            left = []
            right = []
            if n.left != None:
                left = inorder(n.left)
            if n.right != None:
                right = inorder(n.right)
            return left + [n.val] + right
            
        treeA = inorder(root1)
        treeB = inorder(root2)

        a, b = 0, len(treeB)-1
        while a < len(treeA) and b > -1:
            sum_ = treeA[a] + treeB[b]
            if sum_ == target:
                return True
            elif sum_ < target:
                a += 1
            else:
                b -= 1

        return False

참고:

- https://leetcode.com/problems/two-sum-bsts/description/