LeetCode: 98번 (Validate Binary Search Tree) [JAVA]

문제 링크

https://leetcode.com/problems/validate-binary-search-tree/

Validate Binary Search Tree - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 큐를 생성 후, 주어진 이진 탐색 트리를 중위 순회로 돌며 해당 노드의 값을 큐에 저장
   
2. 큐에서 값을 하나씩 빼어, 해당 값들이 모두 오름차순인지를 파악
3. 오름차순으로 정렬되어 있지 않다면 false를 반환하고, 정렬되어 있다면 true를 반환

 이진 탐색의 특징 중 하나를 활용하여 쉽게 문제를 풀 수 있다. 바로 맞게 구성된 이진 탐색 트리를 중위 순회로 값을 출력하게 되면, 일정하게 오름차순으로 정렬되어 숫자들이 출력된다. 이를 이용해, 전체적으로 중위 순회를 통해 트리를 돌며 그 때 노드의 숫자들을 큐에 저장한 다음, 순회가 끝나고 큐에 저장된 숫자들이 오름차순으로 정렬되어 있는 지를 체크해주면 된다. 이 때 정렬이 되어 있다면 true를, 그렇지 않다면 false를 반환하면 된다. 

 

class Solution {
    Queue<Integer> q = new LinkedList<>();

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        inorderTraversal(root);

        int prevValue = q.poll();//최초값 pop

        while (!q.isEmpty()) {//모든 값을 돌며
            int nowValue = q.poll();

            if (prevValue >= nowValue) {//순서가 맞지 않는다면
                return false;
            }

            prevValue = nowValue;
        }

        return true;
    }

    void inorderTraversal(TreeNode node) {//중위 순회
        if (node == null) {
            return;
        }

        inorderTraversal(node.left);
        q.add(node.val);
        inorderTraversal(node.right);
    }
}

결과