LeetCode 98(Validate Binary Search Tree, java)

0. 문제

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

Validate Binary Search Tree - LeetCode

 

1. 문제 설명

- 문제에서 이진트리(root)가 주어진다.

- 주어진 이진트리가 이진 탐색 트리를 만족하는지 판단하는 것이 문제의 핵심이다. 

 

2. 문제 해설

a) 첫 번째 접근

- 이 문제는 이진 탐색 트리의 조건을 만족하는지를 판단하는 문제다.

 

- 그러므로 다음과 같은 조건이 만족되어야 한다.

  → 좌측 자식 노드는 부모 노드보다 작은 값을 가져야 한다.

  → 우측 자식 노드는 부모 노드보다 큰 값을 가져야 한다. 

 

- 그러나 이 규칙만을 보고 간과하는 케이스가 한 가지 존재한다. 

  ex) [5, 1, 4, null, null, 3, 6]  

  → 노드(4)는 좌측에 3, 우측에 6의 자식 노드를 갖는다. 

  → 그러나 올바른 BST라면, 좌측 노드(3)는 좌측 노드(1)의 우측 자식이어야 마땅하다. 

  → 그 이유는 좌측의 자식 노드(3)은 루트 노드(5)보다 작은 값을 가지기 때문이다. 

 

- 여기까지 문제 해결에 필요한 비교 방법은 다 나왔다.

 

b) 두 번째 접근

- 루트 노드를 시작점으로 생각해보자. 

- 좌측 자식 노드는 루트 노드보다 작은 값을 가진다.

- 우측 자식 노드는 루트 노드보다 큰 값을 가진다. 

 

- 즉, 노드가 삽입될 때 루트의 값을 기준으로 좌/우측의 방향이 결정된다.

- 그러므로 매번 좌/우측 노드를 탐색할 때마다 루트 노드의 값을 기준으로 비교하면 되는 것이다. 

 

- 다시 쉽게 설명하자면 다음과 같다.

  → 루트의 첫 번째 좌측 자식 노드 아래에 존재하는 모든 하위 노드는 무조건 루트보다 작은 값을 가진다.

  → 루트의 첫 번째 우측 자식 노드 아래에 존재하는 모든 하위 노드는 무조건 루트보다 큰 값을 가진다.

 

- 그렇다면 여기서 한 가지 의문이 든다.

- 최초에 루트의 값은 무엇으로 비교해야 할까? 

 

c) 세 번째 접근

- 이에 대한 힌트는 문제의 제약조건에서 파악할 수 있다.

 

- 문제에서 주어진 제약조건은 노드가 가질 수 있는 수의 범위를 의미한다.

- 어딘가 익숙한 표현 범위라는 느낌이 오지 않는가? 

 

- 이는 정수의 표현 범위와 동일하다. 

 

- 그렇다면 정수의 최대 값과 최소 값으로 비교하면 되겠다.라고 생각했다면 이는 오산이다.

- 노드는 정수의 표현 범위를 갖는다. 그러므로 비교를 위해서는 더 큰 단위의 수가 필요하다.

- 결과적으로 Long 자료형을 사용해야 한다.  

 

- 이제 이 과정을 재귀 함수로 구현하면 끝이다.

 

3. 정답 코드

class Solution {
    public boolean isValidBST(TreeNode root) {
        return checkBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    public boolean checkBST(TreeNode root, long min, long max) {
        if(root == null) {
            return true;
        }
        
        if(root.val <= min || root.val >= max) {
            return false;
        }
        
        return checkBST(root.left, min, root.val) && 
               checkBST(root.right, root.val, max);
    }
}