Leetcode - Validate Binary Search Tree

문제

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

Validate Binary Search Tree - LeetCode

 

풀이

root부터 시작하여 왼쪽 서브트리는 계속 작아져야 하고 오른쪽 서브트리는 계속 커져야 한다는 게 문제의 핵심이다.

 

따라서 서브 트리가 유효한 지 확인할 때는 서브 트리가 가질 수 있는 최소값과 최대값을 어딘가에 저장하고 있어야 한다.

 

풀이에서는 isValidBST에 minValue, maxValue를 들고 다닐 수 있도록 메서드를 오버라이딩해서 구현했다.

 

풀이를 차례대로 생각해보면,

 

1) 최초 진입 시점에는 루트 노드이므로 min, max에 대한 제한이 없기 때문에 null로 초기화한다.

2) 서브 트리로 진입한 이후에는 현재 노드 값이 최솟값, 최댓값 조건에 어긋나면 false를 리턴한다.

3) 왼쪽 서브트리의 유효성은 maxValue를 현재 노드의 값으로 갱신하여 물려준다.

4) 오른쪽 서브트리의 유효성은 minValue를 현재 노드의 값으로 갱신하여 물려준다.

/**
 * 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, null, null);
    }
    
    public boolean isValidBST(TreeNode root, Integer minValue, Integer maxValue) {
        if (root == null) {
            return true;
        }        
        
        if ((minValue != null && root.val <= minValue) || (maxValue != null && root.val >= maxValue)) {
            return false;
        }
        
        if (!isValidBST(root.left, minValue, root.val) || !isValidBST(root.right, root.val, maxValue)) {
            return false;
        }
        
        return true;
    }
}