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

문제 바로가기

BFS

처음에는 BFS로 순회하면서 이진탐색을 수행하자고 생각했다.

Time complexity : O(nlogn). 모든 노드를 순회하며 이진탐색
Space complexity : O(n). queue

# 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: TreeNode, k: int) -> bool:
        self.queue = [root]
        return self.BFS(root, k)
        
    def BFS(self, root: TreeNode, k: int) -> bool:
    	# 탐색 실패 조건
        if not self.queue:
            return False
        
        targetNode = self.queue.pop(0)
        if targetNode.left:
            self.queue.append(targetNode.left)
        if targetNode.right:
            self.queue.append(targetNode.right)
        
        diff = k - targetNode.val
        node = root
        
        while node:
            # 탐색 성공 조건
            if diff == node.val and node != targetNode:
                return True
            elif diff < node.val:
                node = node.left
            else:
                node = node.right
        
        return self.BFS(root, k)

문제를 풀고 솔루션을 확인했는데... 세상에, 이진탐색트리는 중복된 노드가 없다는 것을 잊고 있었다.
이를 반영해 다시 작성했다.

DFS + set

Time complexity : O(n). 모든 노드를 순회
Space complexity : O(n). set

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        self.numSet = set()
        return self.DFS(root, k)
        
    def DFS(self, node: TreeNode, k: int) -> bool:
        if not node:
            return False
        if k - node.val in self.numSet:
            return True
        self.numSet.add(node.val)
        return self.DFS(node.left, k) or self.DFS(node.right, k)

BST

BST를 inorder 방식으로 읽으면 정렬된 list를 얻을 수 있다는 점을 활용한 방법.
하지만 결과만 놓고보면 DFS 보다 더 많은 메모리와 시간을 소모했다.

Time complexity : O(n). 모든 노드를 순회 + list 읽음
Space complexity : O(n). list

# BST 활용
class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        self.sortedList = list()
        self.inorder(root)
        idxL = 0
        idxR = len(self.sortedList) - 1
        while idxL != idxR:
            sumVal = self.sortedList[idxL] + self.sortedList[idxR]
            if sumVal == k:
                return True
            elif sumVal < k:
                idxL += 1
            else:
                idxR -= 1
                
        return False
        
    def inorder(self, node: TreeNode) -> bool:
        if not node:
            return
        self.inorder(node.left)
        self.sortedList.append(node.val)
        self.inorder(node.right)