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

문제

 

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

Two Sum IV - Input is a BST - LeetCode

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

BST에서 두개의 요소가 target이랑 값이 같으면 true, 아니면 false를 반환하라

 

Example 1:

Input	Output
root = [5,3,6,2,4,null,7], k = 9	true

Example 2:

Input	Output
root = [5,3,6,2,4,null,7], k = 28	false

 

 

문제풀이 코드

# 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:
        lst = []
        return dfs(root, lst, k)

def dfs(root, lst, val):
    if not root:
        return False
    
    if (val - root.val) in lst:
        return True
    
    lst.append(root.val)
    return dfs(root.left, lst, val) or dfs(root.right, lst, val)

dfs로 접근하여 문제 풀이

1. root가 None일 때는 False를 리턴하고

2. val -  root.val이 lst안에 있다면 True를 반환(root.val + lst안에 어떤 값 = val)

3. lst에 root.val을 넣어주면서 dfs를 호출하여 비교 

•    return A or B => A 와 B둘다 참일 때 A를 반환
•    return A or B => A 와 B둘다 거짓일 때 B를 반환
•    return A or B => A와 B 중 하나만 참일 때 참인값을 반환