[Algorithm] Binary Tree + 530. Minimum Absolute Difference in BST

리트코드 530. Minimum Absolute Difference in BST

Binary Search Tree에 있는 전체 노드의 차이 중 가장 적은 숫자를 리턴한다. (서로 부모-자식 관계인 노드가 아니여도 됨)

115ms가 걸린 내 코드랑 디스커션에 있는 55ms 걸린 코드를 비교해보려고 한다.

나는 단순하게 전체 노드를 저장해서 가장 작은 차이를 골랐는데, BST의 성질을 이용하지 못했다. 디스커션의 코드는 왼쪽 자식 노드가 항상 부모 노드보다 작고, 오른쪽 자식 노드가 항상 부모 노드보다 크다는 것을 이용했다.

 

< 디스커션에 있는 코드 >  55ms

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        def fn(node, lo, hi):
            if not node: 
                return hi - lo
            
            left = fn(node.left, lo, node.val)
            right = fn(node.right, node.val, hi)
            return min(left, right)
        
        return fn(root, float('-inf'), float('inf'))

 

< 내 코드 > 115ms

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        res = []
        res.append(root.val)
        self.dfs(root, res)
        res.sort()
        
        ans = []
        for i in range(len(res) - 1):
            ans.append(abs(res[i+1] - res[i]))
        return min(ans)
        
    
    def dfs(self, root, res):
        if root.left:
            res.append(root.left.val)
            self.dfs(root.left, res)
        if root.right:
            res.append(root.right.val)
            self.dfs(root.right, res)