783. Minimum Distance Between BST Nodes

1. 그냥 트리를 돌고서 li를 sort

# 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 minDiffInBST(self, root: Optional[TreeNode]) -> int:
        li=[]
        def sol(root):
            li.append(root.val)
            if root.left:
                sol(root.left)
            if root.right:
                sol(root.right)
        sol(root)
        li = sorted(li)
        answer=100000000
        for x, y in zip(li[:-1],li[1:]):
            answer = min(answer, abs(x-y))
        return answer

 

그런데 BST라는 의미는 in-order로 정렬할 때 오름차순으로 정렬된다는 특징이 있다는 것!

아래는 BST 성질을 이용해서 푼 경우. 그냥 그때그때 보면서 업데이트 해줘도 된다(제출할 땐 print 빼기)

 

# 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 __init__(self, prev=100000000, m=100000000):
        self.prev = prev
        self.m = m
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        def sol(root):
            if root.left:
                sol(root.left)
            self.m = min(abs(self.prev-root.val), self.m)
            print(self.m, self.prev)
            self.prev=root.val
            
            if root.right:
                sol(root.right)
        sol(root)
        return self.m

 

 

그런데 위가 속도가 더 빠른데, 아마도 abs 때문이라고 생각된다.

파이썬은 dynamic 한 타입형 때문에 비교할 때에도 비교할 객체 타입 비교부터 하기 때문에 속도가 느리다.

abs를 없앴으나 더욱 느려지는 대참사가 나고 있음.. 나중에 생각해 볼 예정

# 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 __init__(self, prev=-100000000, m=100000000):
        self.prev = prev
        self.m = m
        
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        def sol(root):
            if root.left:
                sol(root.left)
            self.m = min(root.val-self.prev, self.m)
            self.prev=root.val
            if root.right:
                sol(root.right)
        sol(root)
        return self.m