[LeetCode 98.] Validate Binary Search Tree (Java)

문제

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

트리가 주어지는데, 이 트리가 이진트리인지 판단한다.

 

풀이

 

1. 특정 노드를 기준으로, 왼쪽 자식 노드는 (B)는 부모노드(A)보다 값이 작아야하고, 오른쪽자식노드(C) 보다 커야한다.

B의 왼쪽 자식노드(D)는 B보다 작아야하며, 오른쪽 자식노드(E)는 B보다 커야되고, A보다는 작아야한다.

 

1. root 부터 isValidBST 함수를 실행한다.

* 이때 노드의 범위가 정수 범위이므로, Long 값의 최대, 최소값을 세팅해준다.

2. isValidBST() 함수에서 node가 null이면, true이다.

3. node의 값이 min 보다 작거나 같다면 false를 반환한다.

4. node의 값이 max 보다 크거나 같다면 false를 반환한다.

5. 왼쪽 자식노드가 유효한지 확인한다.

5-1.

isValidBST() 함수를 재귀 호출한다. 인자로 왼쪽 자식노드 node.left, 최소값으로 min 그리고 최대값으로 현재 노드의 값 node.val을 전달한다. (왼쪽 자식노드는 부모 노드보다 작아야 하기 때문에 최대 한계값으로 현재 노드의 값을 전달한다.)
5-2. 왼쪽 자식노드가 유효하지 않다면 false를 반환한다.

6. 오른쪽 자식노드가 유효한지 확인한다.
6-1. isValidBST() 함수를 재귀 호출한다. 인자로 오른쪽 자식노드 node.right, 최소값으로 현재 노드의 값 node.val 그리고 최대 한계값 max를 전달한다. (오른쪽 자식노드는 부모 노드보다 커야 하기 때문에 최소 한계값으로 현재 노드의 값을 전달한다.)
6-2. 오른쪽 자식노드가 유효하지 않다면 false를 반환한다.

 

7. 최종적으로 모든 노드가 유효하다면 true를 반환한다.

 

Java Code

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