[LeetCode] 98. Validate Binary Search Tree - 이진탐색트리(Binary Search Tree) JAVA

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

코드설명

이진탐색트리(Binary Search Tree) 를 활용합니다.

 

각 코드 상단에 설명사항을 작성했습니다. 

코드

정답코드1입니다. 이 코드는 중위순회를 활용해서 BinarySearch Tree를 순회하고, 그 값이 반드시 정렬되어있어야만 올바른 BinarySearch Tree임을 활용합니다. 결과를 제출해보면, beats 22% 정도로 비교적 느린 결과를 반환하고 있습니다.

/**
 * 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) {
        List<Integer> arr = new ArrayList<>();
        midOrder(root, arr);
        // return midOrder(root);

        int now = arr.get(0);
        for(int i=0; i<arr.size() - 1; i++){
            if(arr.get(i) >= arr.get(i + 1)){
                return false;
            }
        }
        return true;
    }

    void midOrder(TreeNode now, List<Integer> arr){
        if(now == null) return ;
        midOrder(now.left, arr);
        arr.add(now.val);
        midOrder(now.right, arr);
    }
}

 

처음에 작성한 코드입니다. 

이진 탐색 트리의 RootTree의 LeftTree에는 항상 LeftTree 전체보다 커야합니다.

반대로, RootTree의 rightTree에는 항상 rightTree 전체보다 작아야 합니다.

아래 코드는 해당사항을 고려하지 않고, 오직 LeftTree의 Value값, rightTree의 Value값만 고려하고 있습니다.

/**
 * 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 DFS(root;
    }

    boolean DFS(TreeNode now){
        boolean ret = true;
        if(now.left != null){
            if(now.val <= now.left.val){
                return false;
            }
            ret &= DFS(now.left);
        }

        if(now.right != null){
            if(now.val >= now.right.val){
                return false;
            }
            ret &= DFS(now.right);
        }

        return ret;
    }
}

 

마지막 정답코드입니다. 이 코드가 가장 빠른데요.

특징은, maximum과 minimum을 활용하여 자식노드에서 Parent의 Parent의 범위값을 구할 수 있다는 점입니다.

즉, 현재 now의 value가 다음 쿼리 값의 minimum 혹은 maximum이 된다는 점입니다.

/**
 * 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);
    }

    boolean valid(TreeNode now, long minimum, long maximum){
        if(now == null) return true;
        if( !(now.val > minimum && now.val < maximum) ){
            return false;
        }
        return valid(now.left, minimum, now.val) & valid(now.right, now.val, maximum);
    }
}