문제

트리에 있는 서로 다른 두 노드의 값 사이의 최소 절대 차이를 구해야한다.

구현 전 예상 풀이

1. 노드를 방문하면 기존에 리스트에 넣어둔 노드와 차이를 구한다.
2. 차이의 절대값과 기존 최소값과 비교한다.
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) {
        return visitRec(root, new ArrayList<>(), Integer.MAX_VALUE);
    }

    private int visitRec(TreeNode node, List<Integer> list, int min) {
        if (node == null) {
            return Integer.MAX_VALUE;
        }

        int val = node.val;

        for (Integer v : list) {
            min = Math.min(min, Math.abs(val - v));
        }

        list.add(val);

        min = Math.min(min, visitRec(node.left, list, min));
        min = Math.min(min, visitRec(node.right, list, min));

        return min;
    }
}

개선점

중요한 포인트를 놓치고 문제를 풀었다.
그건 바로 문제에서 주어진 트리가 Binary Search Tree (BST)이다!!!
BST는 중위순회를 하면 오름차순으로 정렬된 배열과 값이 같다.
1. BST를 중위순회한다.
2. 노드를 방문할 때마다 이전 노드와 차이를 구한다.
3. 이전에 구한 최소값과 비교한다.

class Solution {
    TreeNode pre = null;

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

        int min = getMinimumDifference(root.left);

        if (pre != null) {
            min = Math.min(min, root.val - pre.val);
        }

        pre = root;

        min = Math.min(min, getMinimumDifference(root.right));

        return min;
    }
}

시간복잡도가 개선되었다.

530. Minimum Absolute Difference in BST
참고한 풀이 링크