[Grind75-LeetCode] Validate Binary Search Tree JAVA

반응형

728x90

[Grind75-LeetCode] Validate Binary Search Tree - Medium

---

접근

• 재귀

---

풀이

BST(Binary Search Tree) 이진 탐색 트리를 검증하는 문제이다. 주어지는 트리를 보고 이진 탐색 트리가 맞는지 확인지만 확인하면 되는 문제로 이진 탐색 트리가 어떤 건지 알아야 하는 문제다. 

 

이진 탐색 트리는 이진트리의 형태를 가진 자료구조로 효율적인 데이터 저장과 검색을 위해 사용된다. 이진 탐색 트리의 특징은 모든 왼쪽 서브트리에 있는 값은 루트 노드의 값 보다 작아야 하고 모든 오른쪽 트리에 있는 값은 루트 노드의 값 보다 커야 한다. 이러한 특징이 재귀적으로 적용되기 때문에 단순 부모 노드의 값 보다만 작고 크면 되는 것이 아니라 해당 노드보다 상위레벨에 있는 모든 노드보다 작거나 커야 한다. 

잘못된 BST

 

위의 그림은 잘못된 BST이다. 6의 왼쪽 서브트리가 3으로 6보다 작고 오른쪽 서브트리가 7로 6보다 커 정상적인 BST를 구성하고 있는 것 같다. 3은 6의 왼쪽 서브트리 조건은 만족하지만 전체적으로 봤을 때 루트 노드인 5의 오른쪽 서브트리에 위치하므로 5의 오른쪽 서브트리 조건도 만족해야 한다. 그러나 3은 5보다 작아 오른쪽 서브트리 조건을 만족하지 못해 위의 트리는 올바른 BST가 아니게 된다.

 

그리고 또 이 문제에는 한 가지 주의할 점이 있다. 이 문제에서 트리 각 노드의 최댓값이 정수형으로 표현가능한 최대와 최소이므로 경곗값 비교 시 원하지 않는 결과가 나올 수 있다. 코드를 통해 다시 설명하겠다.

    public boolean isValidBST(TreeNode root) {
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean valid(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        }

        if (node.val <= min || node.val >= max) {
            return false;
        }

        return valid(node.left, min, node.val) && valid(node.right, node.val, max);
    }

최댓값과 최솟값을 변수에 따로 할당해 비교를 한다. 위 트리 그림과 같이 모든 상위 레벨에 대한 조건을 만족해야 하기에 해당 부분 체크를 위해 사용하는 것이다. 우선 노드가 비었다면 모든 노드가 조건을 만족한 채 검사가 끝나 true를 반환한다. 그리고 노드의 값이 최솟값 보다 작거나 최댓값 보다 클 경우 false를 반환하게 되는데 재귀 호출 내용을 보면 이해할 수 있다. 왼쪽 서브트리는 현재 노드보다 값이 작아야 하니 현재 노드의 값을 max로 설정한 뒤 다음 작업을 수행하고 오른쪽 서브트리는 현재 노드보다 값이 커야 해 현재 노드 값을 min으로 설정한다. 그렇게 되면 다음 노드의 자식과 다음 노드의 부모값을 비교하여 2 레벨 차이로 조건을 만족시키며 진행하기 때문에 올바른 결과를 얻을 수 있다. 

 

min과 max를 비교하는 과정에서 Integer.MIN_VALUE, Integer.MAX_VALUE를 사용한다면 최대나 최솟값 입력 시 이상 이하 조건에서 잘못된 비교가 일어날 수 있다. 경곗값으로 인한 오류를 방지하기 위해 long 타입을 사용해 주어야 한다.  

---

전체 코드

/**
 * 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 boolean isValidBST(TreeNode root) {
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean valid(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        }

        if (node.val <= min || node.val >= max) {
            return false;
        }

        return valid(node.left, min, node.val) && valid(node.right, node.val, max);
    }
}