[leetcode] 98. Validate Binary Search Tree

binary search tree가 정상적인지 체크하는 문제입니다.

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

Validate Binary Search Tree - LeetCode

간단한 문제이나 recursion에 익숙하지 않으면 은근히 어려워 할 수도 있는 문제입니다.

 

왼쪽 substree의 모든 노드가 root보다 작아야 합니다.

오른쪽 subtree의 모든 노드는 root보다 커야 합니다.

 

처음에는 아래와 같이 풀었었습니다.

class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        
        if(root.left != null && root.left.val >= root.val) return false;
        if(root.right != null && root.right.val <= root.val) return false;
                
        boolean left = isValidBST(root.left);
        boolean right = isValidBST(root.right);

        return left && right;
    }
}

그런데 이상하게 wrong answer가 나오는 겁니다!!

자세히 보니... 이렇게 풀면 아래와 같은 케이스는 해결할 수 없었습니다. 3이 5보다 작은데도 5의 오른쪽 subtree의 원소인 것 상황이 커버되지 않았습니다.

   5

 /      \

1         6

           /  \

          3     7

즉, 두 레벨 이상의 노드끼리는 BST임이 보장되지 않았습니다.

 

그래서 노드값의 유효성을 체크할 때 현재 사용이 가능한 최대값과 최소값도 알고 있어야 했습니다.

helper method를 하나 만들어주고,

현재 노드에서 사용할 수 있는 노드의 최대값과 최소값은 파라미터로 넘겨주어 이를 비교하는 로직을 추가해주는 것으로 해결했습니다.

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

    public boolean search(TreeNode root, long max, long min) {
        if(root == null) return true;
        if(max <= root.val || min >= root.val) return false;

        boolean left = search(root.left, root.val, min);
        boolean right = search(root.right, max, root.val);

        return left && right;
    }
}