530. Minimum Absolute Difference in BST

문제 링크: https://leetcode.com/problems/minimum-absolute-difference-in-bst/

문제

이진 검색 트리(BST)의 루트가 주어졌을 때, 트리에 있는 서로 다른 두 노드의 값 사이의 최소 차이의 절대값을 반환하자

나의 풀이

접근

이진 검색 트리의 특성(노드의 왼쪽은 노드보다 작은 값, 노드의 오른쪽은 노드보다 큰 값)을 생각하면, 이웃하는 노드의 값 차이가 아마 가장 작을 거라는 생각이 들었다.

그렇다면 재귀적으로 두 이웃한 노드의 차이를 탐색하면서, 계속 최소값을 업데이트하면 되지 않을까?

구현 코드

아래의 코드는 테스트 케이스는 통과했지만, 전체 테스트 케이스는 통과하지 못했다.

class Solution {
    public int getMinimumDifference(TreeNode root) {
        return getDifference(root, 10000000);
    }

    public int getDifference(TreeNode node, int differ) {
        if (node == null)
            return differ;
        int leftDifference = (node.left != null) ? Math.abs(node.val - node.left.val) : differ;
        int rightDifference = (node.right != null) ? Math.abs(node.val - node.right.val) : differ;

        int left = getDifference(node.left, leftDifference);
        int right = getDifference(node.right, rightDifference);
        return Math.min(left, right);
    }
}

---

다른 풀이

하지만 간과한 점이 있었다.

BST 특징

• root 노드의 이전 값: 왼쪽 하위 노드 중 가장 큰 값
• root 노드의 다음 값: 오른쪽 하위 노드 중 가장 작은 값

위 특징을 이용해, 현재 노드와 차이를 계산하는 이전 노드는 바로 이웃한 노드가 아닌, 위의 노드가 되어야 한다는 점이다.

다음 코드는 트리의 중위 순회를 이용한 방식이다.

public class Solution {
    
    int minDiff = Integer.MAX_VALUE;
    TreeNode prev;
    
    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        return minDiff;
    }
    
    public void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        if (prev != null) minDiff = Math.min(minDiff, root.val - prev.val);
        prev = root;
        inorder(root.right);
    }

}

• 해당 노드의 왼쪽 하위 트리의 끝까지 내려간다
• 끝까지 내려간 후, 그 노드의 오른쪽 하위 트리를 탐색
• prev노드 왼쪽 하위 트리의 가장 오른쪽 노드로 선정