•
문제 설명 : 제공된 이진 탐색 트리에서 두 노드의 차이 값 중 가장 작은 절대 값을 반환
•
풀이 방법
◦
이진 탐색 트리는 왼쪽 자식 노드가 현 노드보다 반드시 작고, 오른쪽 자식노드는 현 노드보다 반드시 크다.
◦
따라서, 가장 차이가 적은 절대값은 2가지 경우이다.
▪
| 현 노드 값 - 왼쪽 하위 트리의 가장 우측 Leef Node |
▪
| 현 노드 값 - 오른쪽 하위 트리의 가장 왼쪽 Leef Node |
•
시간복잡도 :
•
성공 코드
# 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 getMinimumDifference(self, root: Optional[TreeNode]) -> int:
self.min_num = float(inf)
def search_tree(node):
if not node.left and not node.right:
return node.val
# 좌측 자식 노드들은 모두 현 노드보다 작다.
# 따라서, 좌측 자식 노드 중 가장 큰 노드와 현 노드의 차이를 비교한다.
# 각 노드마다, 한쪽 노드를 탐색함 O(LogN)
if node.left:
search_tree(node.left)
self.min_num = min(self.min_num, abs(node.val - leef_right_node(node.left)))
# 우측 자식 노드들은 모두 현 노드보다 크다.
# 따라서, 우측 자식 노드 중 가장 작은 노드와 현 노드의 차이를 비교한다.
# 각 노드마다, 한쪽 노드를 탐색함 O(LogN)
if node.right:
search_tree(node.right)
self.min_num = min(self.min_num, abs(node.val - leef_left_node(node.right)))
# 좌측 자식 노드가 없을 떄까지 계속 탐색하여 가장 작은 하위 노드를 찾는다.
def leef_left_node(node):
if not node.left:
return node.val
return leef_left_node(node.left)
# 우측 자식 노드가 없을 떄까지 계속 탐색하며 가장 큰 하위 노드를 찾는다
def leef_right_node(node):
if not node.right:
return node.val
return leef_right_node(node.right)
search_tree(root)
return self.min_num
Python
복사