•
문제 설명 : 두 노드의 값을 합쳤을 때 제공된 값을 만들 수 있는 트리인지를 반환
•
풀이 방법
◦
두 노드의 값이라는건 결국 [val] + [k-val] 두 노드로 진행되는 것이다
◦
즉, 노드 하나로 Two Sum을 구성하는데 필요한 값을 바로 알 수 있는 것이다.
▪
이를 이용하여, 각 노드가 몇개씩 존재하는지 탐색하였다.
◦
탐색이 끝난 후, 노드 정보를 확인하여 Two Sum 구성이 가능한 트리였는지 반환한다.
•
시간복잡도 :
•
성공 코드
# 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 defaultdict
class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
self.node_info = defaultdict(int)
def search_tree(node):
if not node:
return
if node.left:
search_tree(node.left)
if node.right:
search_tree(node.right)
# 해당 노드 값의 갯수 증가
self.node_info[node.val] += 1
search_tree(root)
# 최소 2개의 노드가 존재하는지 확인
if len(self.node_info) >= 2:
for item in self.node_info:
# Two Sum 을 구성하기 위한 나머지 숫자도 존재하는지 확인
if k - item in self.node_info:
# 만약 동일한 숫자라면, 해당 숫자를 가진 노드가 2개 이상 존재하는지 확인
if item == k - item and self.node_info[item] >= 2:
return True
# 다른 숫자의 조합이라면, 바로 True 반환
elif item != k - item:
return True
return False
Python
복사
•
성공코드2
개인적으로 첫 코드는 가독성도 별로고, 무조건 모든 트리를 탐색한다는 점이 아쉬웠다.
1.
Two Sum 확인 로직의 가독성
•
별도의 메서드로 분리
2.
무조건 모든 노드를 탐색
•
left/right 하위 노드 탐색 전, 현 노드에 대한 정보를 먼저 확인하여 조건에 맞다면 바로 Return → 추가 하위 탐색을 하지 않는다.
코드 제출 시에는 첫 방식과 큰 시간차이는 없었지만, 만약 대량의 노드가 존재하는 트리라면 확실한 시간 감소가 있을 것 같다.
# 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 defaultdict
class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
self.node_info = defaultdict(int)
def search_tree(node):
# 해당 노드 값의 갯수 증가
self.node_info[node.val] += 1
if not node.left and not node.right:
return check_other_node(node.val)
# 하위 탐색 전, 현 노드가 Two Sum 조건에 맞는지 확인
if check_other_node(node.val):
return True
left = search_tree(node.left) if node.left else False
right = search_tree(node.right) if node.right else False
return left or right
def check_other_node(val):
'''
# Two Sum 을 구성하기 위한 나머지 숫자도 존재하는지 확인
'''
if k - val in self.node_info:
# 만약 동일한 숫자라면, 해당 숫자를 가진 노드가 2개 이상 존재하는지 확인
if val == k - val and self.node_info[val] >= 2:
return True
# 다른 숫자의 조합이라면, 바로 True 반환
elif val != k - val:
return True
return search_tree(root)
Python
복사