Two Sum IV - 입력이 BST임

이진 검색 트리의 루트와 대상 번호 k가 주어지면 BST에 두 개의 요소가 존재하여 합계가 주어진 대상과 같으면 true를 반환합니다.

Example 1:

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

접근하다

This question is similar to finding if their are two elements in an array such that their sum is equal to the given target.

This problem can be solved either using BFS or DFS. We will solve this using level order traversal(BFS) which uses queue data structure for tree traversing.

The idea here is initialize an empty set , for every node check if target-node.value is available in set , if it is available return True , else add that node value to the set.

At the end directly return False as there is no such elements present in BST.

The reason why I have chosen set for storing the node values is , insert and retrieve operations on set can be done in O(1) time complexity as internally set is implemented using Hashing.

암호

from collections import deque
# 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:
        queue = deque()
        queue.append(root)
        available = set()
        while len(queue)>0:
            popped = queue.popleft()
            if k-popped.val in available:
                return True
            else:
                available.add(popped.val)
            if popped.left:
                queue.append(popped.left)
            if popped.right:
                queue.append(popped.right)
        return False

Note: If anyone want to more about level order traversal of a tree , please let me know in comments. I will write a detailed post on level order traversal.