문제

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

해결 방법

• BST의 특징인 left < root < right 을 사용

• 주이전 BST를 중위순회로 조회한다면 정렬된 리스트를 얻을 수 있음

• ex) 아래와 같은 트리가 있을 때, 중위 순회를 하면 [1, 3, 5, 6, 10]을 얻을 수 있음
  

• 이제 최소 차이를 구해야 하는데 정렬된 리스트에서는 바로 앞, 뒤 값의 차이 중 최소 차이가 존재하기 때문에 O(n)의 시간 복잡도를 가짐

• 여기서 이 값들을 List나 배열에 Tree의 value 값을 저장하려 하였으나 공간 복잡도를 더 줄일 수 있는 방법을 생각해 보았을 때, 전체 리스트가 필요하지 않고 현재 노드와 이전 노드만 알면 된다고 생각함 => 공간 복잡도를 줄일 수 있음

코드

class Solution {

    static int minDiff;
    static TreeNode prev;

    public int getMinimumDifference(TreeNode root) {
        minDiff = Integer.MAX_VALUE;
        prev = null;
        check(root);
        return minDiff;
    }

    private void check(TreeNode now) {
       if (now.left != null) {
           check(now.left);
       }

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

       if (now.right != null) {
           check(now.right);
       }
    }
}

결과