[JAVA][LeetCode][BST] #98. Validate Binary Search Tree

문제 : 

 

예시 : 

 

제한 조건 : 

 

---

 

시도1 : 처음에는 부모랑만 비교하면 된다고 생각했다.

그래서 간단히 정리해본 수도코드와 실제 코드

class Solution {
    public static final int LEFT = 0;
    public static final int RIGHT = 1;

    public boolean isValidBST(TreeNode root) {
        return checkValid(root.left, root.val, LEFT) 
                && checkValid(root.right, root.val, RIGHT);
    }

    private boolean checkValid(TreeNode node, int parentValue, int side) {
        if(node == null) return true;

        // should node.value is smaller thgan parentValue.
        if(side == LEFT && node.val >= parentValue) return false;
        
        if(side == RIGHT && node.val <= parentValue) return false;

        return checkValid(node.left, node.val, LEFT) 
                && checkValid(node.right, node.val, RIGHT);
    }
}

근데 !!

틀려버림

 

보니까 바로 부모만 생각하면 안되고 부모 전체를 생각해야 했었다!!

 

그래서 시도2

class Solution {
    public static final int LEFT = 0;
    public static final int RIGHT = 1;

    public boolean isValidBST(TreeNode root) {
        ArrayList<Integer> parents = new ArrayList<>();

        parents.add(root.val);
        return checkValid(root.left, parents, LEFT) 
                && checkValid(root.right, parents, RIGHT);
    }

    private boolean checkValid(TreeNode node, ArrayList parents, int side) {
        if(node == null) return true;

        // should node.value is smaller thgan parents.
        if(side == LEFT) {
            for(int i=0; i<parents.size(); i++) {
                if(node.val >= (int)parents.get(i)) return false;
            }

            parents.add(node.val);
        } 
        
        // should node.value is greater thgan parents.
        if(side == RIGHT) {
            for(int i=0; i<parents.size(); i++) {
                if(node.val <= (int)parents.get(i)) return false;
            }

            parents.add(node.val);
        } 

        return checkValid(node.left, parents, LEFT) 
                && checkValid(node.right, parents, RIGHT);
    }
}

 

이거는 left 부모도 모두 저장되서 실패..

 

계속 생각해도 모르겠어서 유튜브에 푸는 방법을 검색해보았다.

https://youtu.be/s6ATEkipzow?si=mhnMkeRL7b4cuJE4

 

코드까지 보진 않고 푸는 방법에 대한 힌트만 얻고 혼자 해봄

그냥 간단하게 최소/최대 값을 정하면 되는거였어!!!!

유레카ㅏ아ㅏㅏ!!!

 

그래서 바로 다시 시도

시도3 :

class Solution {
    public boolean isValidBST(TreeNode root) {
        return checkValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean checkValid(TreeNode node, int min, int max) {
        if(node == null) return true;

        if(node.val <= min || node.val >= max) {
            return false;
        }

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

이전에 틀렸던 예제는 넘어갔는데, 문제는 !!!

 

숫자 범위를 항상 생각해야 되는데, 이 부분도 항상 조심해야하는 부분!!

 

쩄든 그래서 Integer -> long으로 변경

 

시도 4:

class Solution {
    public boolean isValidBST(TreeNode root) {
        return checkValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean checkValid(TreeNode node, long min, long max) {
        if(node == null) return true;

        if(node.val <= min || node.val >= max) {
            return false;
        }

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

 

통과아아아!!!!!

 

 

야호 패스했다!!

 

Complexity

Time Complexity : O(n)
Space Complexity : O(n) / However, in a balanced binary tree, the space complexity would be closer to O(log n).

 

https://leetcode.com/problems/validate-binary-search-tree/solutions/4995736/java-solution