LeetCode 530. Minimum Absolute Difference in BST (python)

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

 

 

 

 

풀이

 

이진탐색트리가 주어지면 노드간의 최소 차이값을 찾는 문제이다.

 

최근에 이진탐색트리를 재귀로 구현하는법을 배워서 재귀적으로 만들어봤다.

 

최초코드

import sys
class Solution(object):
    def getMinimumDifference(self, root):
        self.result = sys.maxsize
        def findMin(node):
            if node == None:
                return 
            if node.left:
                self.result =  min(self.result,abs(node.val - node.left.val))
                print(abs(node.val - node.left.val),self.result)
            if node.right:
                self.result = min(self.result,abs(node.right.val - node.val))
                print(abs(node.right.val - node.val),self.result)
            findMin(node.left)
            findMin(node.right)
        findMin(root)

        return self.result

1. result를 전역변수로 최소값을 계산해준다.

2. findMin의 함수로 node의 값과 node.left,node.right의 절대 차이 값을 구한다.(node.left,node.right가 None이 아닐 때 실행)

3. 구해진 절대 차이 값이 result보다 작다면 result 갱신, 

4. findMin 재귀적으로 실행 (left,right) 

 

결과- node에서 left,right값만 계산해주기 때문에 직접적으로 연결되어 있는 노드만 검색하게된다, - > 조부모 노드와 값 비교 불가 

 

 

ex ) [236,104,701,227,911]

 

 

 

이진탐색트리를 순회할 때  중위순회(inorder) 방식을 사용하는데, . (왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회) 중위 순회방식을 사용하게되면 이진탐색트리 내에 있는 모든 값들을 정렬된 순서대로 읽을 수 있다고 한다.  

 

문제에서 노드의 차이가 절대값기준으로 가장 적은 값을 가져와야한다. 정렬된 순서로 탐색을 진행하게되면 앞의 인덱스 값과 비교를 해주며 찾아주면 되겠지?

 

먼저 트리의 제일 deth가 깊은 노드부터 탐색을 시작한다. (제일 작은값)

재귀가 동작되는 순서

 

재귀로 왼쪽 노드 제일 깊은 곳부터 탐색하게 만든다

 

 

 

중위탐색이 되는 순서

 

import sys
class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:     
        self.prev = float('-inf')
        self.res = float('inf')
        
        def findMin(node):
            if node is None:
                return
                                        
            findMin(node.left)
            
            self.res = min(node.val - self.prev, self.res)
            self.prev = node.val

            findMin(node.right)
        
        findMin(root)
        return self.res​

맨 왼쪽 뎁스가 깊은 노드 ( 제일 작은 값) 부터 탐색을 시작하여, 조부모 노드를 후보로 두고 탐색하게 만든다.