653. Two Sum IV - Input is a BST

멍진이·2022년 10월 9일
0

문제

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.

Example 1:

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

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
-10^4 <= Node.val <= 10^4
root is guaranteed to be a valid binary search tree.
-10^5 <= k <= 10^5

코드

# 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
from collections import deque
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        
        q = deque()
        
        q.append([root,k])
        
        while q:
            node, k = q.popleft()                        
            now = node.val
            if k-now != now:
                now = k-now
                answer = self.find_tree(root,now)               
            
                if answer == True:
                    return answer
            if node.left !=None:
                q.append([node.left,k])
            if node.right !=None:
                q.append([node.right, k])
                
        
        return False
    
        
    def find_tree(self,root,val):
        #print(root.val, val)
        tmp = False
        if root.val == val:
            return True
        if root.left == None and root.right == None:
            return False 
        if root.val>val and root.left !=None:
            tmp = self.find_tree(root.left,val)
        elif root.val <val and root.right != None:
            tmp = self.find_tree(root.right,val)
        return tmp

문제 풀이

  • root node부터 집어 넣어서 짝이되는 걸 찾는다.
  • 자기 자신이 복제되지않도록 k-now != now 일때만
  • q에다가 집어 넣어서 끝까지 찾아보도록 한다.

빠른 코드

mapp = set()
mapp.add(k-n.val)
  • set을 이용하여 node의 나머지 값을 찾는다.
profile
개발하는 멍멍이

0개의 댓글