리트코드 - 530. Minimum Absolute Difference in BST

리트코드 - 530. Minimum Absolute Difference in BST

출처 - https://leetcode.com/problems/minimum-absolute-difference-in-bst/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

이진 탐색 트리 (BST)의 루트가 주어질 때, 트리 내의 두 다른 노드 값 간의 최소 절대 차이를 반환하세요,

 

의사코드

prev 노드 선언 함수 최소값     int min = 최대 정수값     minValue 함수(매개변수 root, min) 함수 minValue     if (node == null)         min 리턴        min = minValue(node의 왼쪽, min)     if (prev !=null)         min = min과 (prev의 val값 - node의 val 값 ) 중 작은 값     prev = node     min = minValue(node의 오른쪽, min)     min 리턴

 

풀이코드

class Solution {    
    private TreeNode prev;

    public int getMinimumDifference(TreeNode root) {
        int min = Integer.MAX_VALUE;
        return minValue(root, min);
    }

    private int minValue(TreeNode node, int min) {
        if (node == null) {
            return min; 
        }
        min = minValue(node.left, min);

        if (prev != null) {
            min = Math.min(min, Math.abs(prev.val - node.val));
        }

        prev = node;
        min = minValue(node.right, min);

        return min;
    }
}

코드설명

이중트리노드를 중위 순회하여 값을 찾는 방법이다.

먼저 제일 왼쪽 자식 노드를 방문하여 prev로 만들고 부모 노드의 값을 빼서 최소값이면 갱신한다.

그리고 부모노드를 다시 prev로 만들어서 오른쪽 자식 노드의 값과 차를 비교해서 최소값이면 갱신한다.

 

그리고 오른쪽 자식 노드의 값을 다시 prev로 만들어서 부모의 부모 노드 값 비교하여 뺀다.

왜냐하면 부모 노드 < 오른쪽 자식 노드 < 부모의 부모 노드 값이기 때문이다.

 

위의 예시에서 2가 부모노드라고 가정할 때, 오른쪽 자식 노드(4)는 부모 노드보다는 크지만 부모의 부모 노드(5)보다는 작다.

 

중위 순회에서 중요한 점은 자식노드 끼리의 차는 뺄 필요가 없다는 것이다.

위의 예시에서 2가 부모노드라고 가정할 때, 자식으로 가지는 1과 4 사이 값으로 반드시 부모노드의 값이 존재한다.

즉, 2와 3을 부모로 가질수 있는 것인데 어떤 수가 오더라도 부모-자식의 값이 이 자식끼리의 차보다는 작다.

자식끼리는 값을 뺄 필요가 없는 것이다.

 

이런식으로 왼쪽을 확인하고, 오른쪽을 확인하고 하는 재귀적 구조를 거치면 두 노드의 최소값을 구할 수 있다.

 

시간복잡도 - O(n)

공간복잡도 - O(n) (노드의 갯수만큼의 동적 크기)

 

문제를 풀며 생각한 흐름과 배운 점

초기 생각한 방법

class Solution {
    public int getMinimumDifference(TreeNode root) {
        int min = Integer.MAX_VALUE;

        return minValue(root, min);
    }

    static int minValue(TreeNode node, int min) {
        if (node == null) {
            return min; 
        }
        if (node.left != null) {
            int subtract = Math.abs(node.val - node.left.val);
            if (min > subtract) {
                min = subtract;
            }
            min = minValue(node.left, min);
        } 
        if (node.right != null) {
            int subtract = Math.abs(node.val - node.right.val);
            if (min > subtract) {
                min = subtract;
            }
            min = minValue(node.right, min);
        }
        return min;
    }
}

초기에는 인접한 노드끼리만 뺀 값들을 차로 생각하였고, 테스트 케이스도 통과하였었다.

그런데 문제에서 any two different nodes 라고 되어있었다. 어떤 노드든 상관이 없는 문제였다.

 

재귀적인 호출이 상당히 머리가 아팠지만, 그래도 이진 탐색트리와 중위순회에 대해 이론적으로만 알고 있다가 코딩문제에 구현했다는 점이 몹시 뿌듯했다.

 

단,,, 이러한 문제는 어느정도 답이 정해져 있는 것 같고, 의사코드는 오히려 독이 되는 것 같다.

설명할 때도 그림으로 표현하는게 더 수월한 것 같다.

 

다른코드

class Solution {
    private int minDiff = Integer.MAX_VALUE;
    private TreeNode prev = null;
    
    public int getMinimumDifference(TreeNode root) {
        inorderTraversal(root);
        return minDiff;
    }
    
    private void inorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        
        inorderTraversal(node.left);
        
        if (prev != null) {
            minDiff = Math.min(minDiff, node.val - prev.val);
        }
        prev = node;
        
        inorderTraversal(node.right);
    }
}

이 코드에서는 최소값(min)도 아예 지역변수로 선언해버렸다.

그러다보니 코드가 더 깔끔해졌다. 그리고 생각해보면 prev 값은 항상 node보다 작다. 굳이 Math.abs()를 쓸 필요가 없다.

기본 생각한 흐름은 같으니 조금은 뿌듯하기도 하다.

 

정리

이중탐색트리를 순차적으로 탐색하려면 중위순회를 해야 함.