LeetCode 530 Minimum Absolute Difference in BST

nayu1105·2023년 9월 7일

leetcode 알고리즘

LeetCode

목록 보기

24/28

LeetCode 530 Minimum Absolute Difference in BST

문제

BST(Binary Search Tree) 가 주어진다.

두 노드 간격 중 가장 최소 간격을 구해라.

문제 분석

첫번째 시도(문제)

BST 니까 왼쪽 - 중간 - 오른쪽 순으로 값이 증가한다.

DFS 함수를 만들어, 가장 왼쪽으로 깊이 탐색 후, 다음 오른쪽을 탐색하도록 구현했다.

그런데 아래 코드를 제출하니 계속 오류가 났다.

코드

class Solution {

    static int pre = Integer.MAX_VALUE;
    static int min = Integer.MAX_VALUE;
    static boolean check = false;

    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return min;   
    }

    public void dfs(TreeNode node){
        if(node==null) return;

        dfs(node.left);
        if(!check) check= true;
        else min = Math.min(min, Math.abs(node.val - pre));
        pre = node.val;

        dfs(node.right);
    }
}

두번째 시도(해결)

원인을 찾기 위해 다른 코드를 찾아보니, 다른 코드와 알고리즘이 똑같았다.

코드를 다시 보고 원인을 찾아보니 static 이 문제였다!!!

Solution에 지역변수로 바꾸니 해결되었다.

그리고 check 라는 boolean 변수를 없애고, 가독성을 위해 pre 를 int 가 아닌 TreeNode 객체 선언하였다.

해결된 코드는 아래와 같다.

코드

class Solution {

    TreeNode pre = null;
    int min = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return min;   
    }

    public void dfs(TreeNode node){
        if(node==null) return;

        dfs(node.left);
        if(pre != null) min = Math.min(min, Math.abs(node.val - pre.val));

        pre = node;

        dfs(node.right);
    }
}