[leetcode 530] Minimum Absolute Difference in BST (JAVA)

1.문제

Minimum Absolute Difference in BST - LeetCode

Minimum Absolute Difference in BST - LeetCode

---

2.문제설명

• 주어진 이진 트리에서 인접한 두 노드간의 차이 중 가장 작은 값을 찾으면 되는 문제이다.
• 주어진 이진 트리는 정수 값을 가진다
• BST 의 특징인 중위 순회를 사용 하여 인접한 노드 간의 차이 중 가장 작은 값을 찾는다

---

3.소스코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    
    static int minValue;
    static TreeNode prev;

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

    private void binary_search(TreeNode curr) {
       if (curr.left != null) {
           binary_search(curr.left);
       }

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

       if (curr.right != null) {
           binary_search(curr.right);
       }
    }
}

---

4.소스코드 해설

이 문제의 핵심은 BST 의 중위 순회를 수행 하면서 노드의 값의 차이를 구하는 문제이다.

 

BST 는 재귀적인 구조를 가지고 있어 Binary_Search 함수를 재귀 를 돌면서 트리를 순회한다.

 

BST 를 중위 순회 하면서 각 노드의 값을 추출하고

인접한 두 값 간의 차이를 Math.min(minvalue , 현재 노드 값 - 이전 노드값) 으로 업데이트 한다.

만들어진 minValue 를 반환

---

5.회고

BST 를 수행 하면서 자동적으로 오름차순 정렬 된다는 생각을 하지 못했었고 직접 손으로 그려보았을 때 BST는 자동적으로 오름차순으로 정렬 되겠다는 것을 알게 되었다.

 

오름 차순으로 정렬이 된다면 인접 노드들간의 차이를 계산 하고 최소값을 구현 할 수 있게 되어 금방 문제를 풀게 되었다.

 

 

하지만 재귀함수를 도는 총 N번 호출 되므로 공간 복잡도는 O(N) 이고 

시간 복잡도는 O(NlogN) 의 모든 노드에 대해 한번씩 서브트리를 뒤지기 떄문에 O(NlogN)의 시간 복잡도를 가지게 될것이다.

 

처음 차이를 어떻게 구현 할까 에서 배열이나 노드에 저장 하려 했지만 생각 하면서 그냥 이웃하는 이전 노드만 알고있다면? 이라는 생각으로 풀게 되었다.