[LeetCode/Top Interview 150] [Binary Search Tree (BST)] 530. Minimum Absolute Difference in BST

문제 링크: https://leetcode.com/problems/minimum-absolute-difference-in-bst/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: easy

문제:

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

Input: root = [4,2,6,1,3]
Output: 1

Example 2:

Input: root = [1,0,48,null,null,12,49]
Output: 1

Constraints:

The number of nodes in the tree is in the range [2, 10^4].
0 <= Node.val <= 10^5

Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

전략:

아무 노드끼리의 차이가 가장 작은 경우를 구하려면 트리를 배열로 변환해 전체 노드를 하나의 배열에 넣고 정렬한 후 순차적으로 비교하면 될 것 같다. (BFS)

코드 구현:

/**
 * 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) {
        int min = Integer.MAX_VALUE;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        q.offer(root); // 루트노드
        while (!q.isEmpty()) { // 탐색
            TreeNode now = q.poll(); // 현재 노드
            list.add(now.val); // 현재 노드의 값 추가

            if (now.left != null) {
                q.offer(now.left); // 왼쪽 하위 노드 추가
            }      
            if (now.right != null) {
                q.offer(now.right); // 오른쪽 하위 노드 추가
            }
        }
        Integer[] array = list.toArray(new Integer[0]);
        Arrays.sort(array);
        for (int i=0; i<array.length-1; i++) {
                min = Math.min(min, array[i+1]-array[i]);
        }
        return min;
    }
}
Time: 6 ms (7.94%), Space: 42.8 MB (88.93%) - LeetHub

실행결과:
https://github.com/1-vL/LeetCode/blob/main/0530-minimum-absolute-difference-in-bst/0530-minimum-absolute-difference-in-bst.java

개선 방안:

정렬하지 않고, 처음부터 정렬된 순서로 순회하도록 Stack을 사용하여 왼쪽 하위 노드들부터 탐색하고, 중간 노드, 그 다음 우측 하위 노드들을 탐색하며 즉시 값을 비교한다. (DFS 중위순회)

class Solution {
    int min=Integer.MAX_VALUE;
    int before_val=-1;
    public int getMinimumDifference(TreeNode root) {
        inOrder(root); // 루트노드 중위순회
        return min;
    }
    
    void  inOrder(TreeNode node) {
        if(node == null) { return; } // 리프노드
        inOrder(node.left); // 왼쪽 재귀
        // 이전 값이 존재하면
        if (before_val>=0) {
            // 오름차순 순회이므로 현재값에서 이전값을 뺀 값(차이)가 min보다 작은지 체크
            min = Math.min(min, node.val-before_val);
        }
        before_val = node.val;
        inOrder(node.right); // 오른쪽 재귀
    }
}
Time: 0 ms (100%), Space: 42.7 MB (95.35%) - LeetHub

Solutions 탭의 타인 코드:

// 동일한 중위순회이지만 재귀가 아닌 while 루프로 구현
class Solution {
    public int getMinimumDifference(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        TreeNode curr = root, pre = null;
        int res = Integer.MAX_VALUE;
        while (curr != null || !st.isEmpty()) {
            if (curr != null) { // 현재 위치가 리프노드가 아니라면
                st.push(curr); // 현재 위치 스택에 저장
                curr = curr.left; // 왼쪽으로 계속 이동
            } else { // 리프노드 도달
                curr = st.pop(); // 스택에서 마지막 요소 꺼내어 이동
                // 이전 요소가 있었다면, 비교해서 res(최소값) 갱신
                if (pre != null) res = Math.min(res, curr.val - pre.val);
                pre = curr; // 현재 위치를 이전 위치로
                curr = curr.right; // 오른쪽으로 이동
            }
        }
        return res;
    }
}
Time: 2 ms (25.89%), Space: 43.5 MB (25.21%) - LeetHub

회고:

실제 코테라면 불가능할 정도로 시간을 쓴 것 같다.
그래도 중위순회로 문제가 풀려서 다행이다.