270. Closest Binary Search Tree Value

문제

풀이

class Solution {
    List<Integer> list = new ArrayList<>();
    public int closestBST(TreeNode root, int targetVal) {
        DFS(root);
        int value = -1;
        int min = Integer.MAX_VALUE;
        for(int n : list) {
            if(Math.abs(n - targetVal) < min) {
            min = Math.min(min, Math.abs(n - targetVal));
            value = n; 
            }
             else if(Math.abs(n - targetVal) == min) {
            value = value > n ? n : value;
             }
        }
        return value;
    }

    public void DFS(TreeNode node) {
        if(node == null) {
            return;
        }

        list.add(node.val);

        DFS(node.left);
        DFS(node.right);
    }
}

• DFS로 모든 노드를 탐색해서 list에 넣은 뒤, targetValue와 가장 가까운 값을 구함. 같다면 더 적은 수가 들어간다.
• 하지만, 이 풀이는 모든 노드를 탐색해야하므로 이진 탐색 트리에서는 비효율적인 풀이

BST 풀이

class Solution {
    int answer = Integer.MAX_VALUE;
    public int closestBST(TreeNode root, int target) {
        DFS(root, target);
        return answer;
    }

    public void DFS(TreeNode node, int target) {
        if(node == null) {
            return;
        }

        if(Math.abs(node.val - target) < Math.abs(answer - target)) {
            answer = node.val;
        } else if(Math.abs(node.val - target) == Math.abs(answer - target)) {
            answer = node.val > answer ? answer : node.val;
        }

        if(target < node.val) {
            DFS(node.left, target);
        } else {
            DFS(node.right, target);
        }
    }
}

• target에 더 가까운 값이라면 갱신, 같다면 더 작은 값으로 갱신
• target < node.val 이라면 target과 더 가까운 값은 현재 root 노드 또는 왼쪽에만 존재하므로 root.left탐색
• target > node.val 이라면 target을 더 가까운 값은 현재 root 노드 또는 오른쪽에만 존재하므로 root.right 탐색