Leet code (Medium): 98. Validate Binary Search Tree (재귀) - Java

 

이진트리 법칙을 만족하는지 여부를 판단하는 문제이다.

 

가장먼저 경우의 수에 따른 작은 부분에 대한 문제를 생각했다. 

 

한 단계의 트리만 생각했을 때,

1)

left는 root보다 작아야 한다.

right는 root보다 커야 한다.

 

다만, 한단계 위의 root 까지도 생각해야한다.

2)

root가 left 였다면,

left 는 root 보다 작아야 한다.

right는 root보다 크고 root의 root보단 작아야한다.

 

3)

root 가 right 였다면,

left는 root보다 작고, root의 root보단 커야한다.

right는 root보다 커야한다.

 

 

이를 기반으로 재귀식을 짜면,

boolean 메서드명(노드, 왼쪽 제한 값, 오른쪽 제한 값)

 

따라서 재귀로 코드를 작성하면 다음과 같다.

 

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

    // 재귀를 반복하면서 자연히 min, max 값이 적절히 바뀜.
    // left는 부모보다 작아야하고, 부모가 right였다면 그 윗부모 보단 커야함
    // right는 부모보다 커야하고, 부모가 left였다면 그 윗부모 보단 작아야함
    // 위 두가지에 대응 가능한 재귀 함수임.
    private boolean isValidBST(TreeNode node, long min, long max){
        // 만약 null 이면 무조건 검사할 필요도 없으니 true 리턴 
        if(node == null){
            return true;
        }
        
        if(node.val <= min || node.val >= max){
            return false;
        }

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