[Python] LeetCode - 653. Two Sum IV - Input is a BST

LeetCode 653번 Two Sum IV - Input is a BST 문제는 이진탐색 트리 내의 두개의 숫자로 target 숫자를 만들 수 있는지를 구하느 문제다. 난이도는 하(Easy)이며 Tree 관련 알고리즘을 통해 해결할 수 있다.

 

리트코드 653번 Two Sum IV - Input is a BST 문제 정보

알고리즘 분류

- Tree

난이도

- Easy

 

문제 요약

• 이진탐색트리가 주어지고 target 숫자가 주어졌을 때, BST 내의 두 숫자로 target 숫자를 만들 수 있는 지의 여부를 반환하라.

 

문제 풀이 과정

 

• BST를 타고 내려가면서 타겟 숫자보다 현재 값이 작으면, 나머지 값이 트리에 있는지를 확인한다.

코드

# 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 findNumber(self, root:Optional[TreeNode], num: int) -> bool:
        crnt = root
        while crnt:
            if crnt.val == num:
                return True
            elif crnt.val < num:
                crnt = crnt.right
            else:
                crnt = crnt.left
        
        return False
    
    
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        if not root:
            return False
        
        stack = [root]
        
        while stack:
            crnt = stack.pop()
            targetNumber = k - crnt.val
            if targetNumber != crnt.val and self.findNumber(root, targetNumber):
                return True
            if crnt.left:
                stack.append(crnt.left)
            if crnt.val < k and crnt.right:
                stack.append(crnt.right)
        
        return False

• 시간복잡도: findNumber(): O(logN), findTarget(): O(logN) → O((logN)^2)?
• 공간복잡도: stack 배열 O(logN)