[Binary Search Tree] Minimum Absolute Difference in BST

1. 문제

LeetCode - Minimum Absolute Difference in BST

• 이진 탐색 트리의 루트 노드가 주어졌을 때
• 노드 간 최소 절대 차이값을 반환

2. 접근법

• 먼저, 전위 순회를 통해 List values에 트리의 모든 노드 값을 담아준 뒤, 이중 반복문을 사용하여 최소 절대값을 찾는 방법으로 접근 -> Runtime이 너무 오래걸림(173ms)
• 중위 순회를 했을 때 values의 값들이 정렬되어 있다는 사실 이용 -> 1차원 반복문으로 앞뒤 값만 비교하여 Runtime 1ms로 감소
• ArrayList와 같이 별도의 자료구조를 사용하지 않고 중위 순회를 하면서 이전 노드와 비교하며 최소 절대 차이값을 찾는 방식으로 개선

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 {
    public int getMinimumDifference(TreeNode root) {
        // 1. 트리의 각 노드의 값을 담아줄 ArrayList values
        List<Integer> values = new ArrayList<>();

        // 중위 순회를 통해 values에 모든 값 집어 넣기
        inOrder(root, values); // 중위 순회이므로 values는 정렬되어 있음

        // 2. 최소 차이값 찾기
        int result = Integer.MAX_VALUE;

        // 정렬되어 있으므로 1차원 반복문으로 해결 가능
        for (int i = 1; i < values.size(); i++) {
            int dif = values.get(i) - values.get(i - 1);
            if (dif < result) result = dif; // result = Math.min(result, dif); 도 가능
        }

        return result;
    }

    // 중위 순회
    private void inOrder(TreeNode node, List<Integer> values) {
        if (node != null) {
            if (node.left != null) inOrder(node.left, values);
            values.add(node.val);
            if (node.right != null) inOrder(node.right, values);
        }
    }

}

4. 성능

- Runtime : 173ms -> 1ms -> 0ms

- Memory : 43.7mb

5. 개선

class Solution {
    private int minDif = Integer.MAX_VALUE; // 반환해야 할 최소 절대 차이값, 최대 정수값으로 초기화
    private TreeNode prev = null; // 이전 노드는 inOrder()에서 사용하기 위해 전역 변수 선언 및 null로 초기화

    public int getMinimumDifference(TreeNode root) {
        inOrder(root); // 중위 순회하면서 최소 절대 차이값 구하기
        return minDif;
    }

    // 중위 순회
    private void inOrder(TreeNode node) {
        if (node != null) {
            if (node.left != null) inOrder(node.left);
            if (prev != null) { // 이전 노드가 있으면
                minDif = Math.min(minDif, node.val - prev.val); // 현재 노드와 이전 노드의 값을 비교하여 작다면 업데이트
            }
            prev = node; // 이전 노드 업데이트
            if (node.right != null) inOrder(node.right);
        }
    }

}