LeetCode - 98. Validate Binary Search Tree(BST)

문제

설명

이진 트리의 root가 주어지고 트리가 Binary Search Tree(이하 BST)인지 검증하는 문제다.

BST가 되기 위해선 3가지 조건이 있는데

• 부모 노드의 왼쪽 자식 노드는 부모 노드보다 작아야 한다.
• 부모 노드의 오른쪽 자식 노드는 부모 노드보다 커야 한다.
• 양쪽 서브 트리들은 위 두 가지 성질을 만족해야 한다.

추가적으로 문제에 전제조건이 있는데

• 트리에 있는 노드의 개수는 [$1$, $10^4$] 개다.
• 노드의 값은 [$-2^{31}$, $2^{31}-1$]이다.

풀이

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root, min = -Infinity, max = Infinity) {
    
    if(!root) return true;
    
    if(root.val <= min || root.val >= max) return false;

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

재귀적으로 서브 트리에 있는 자식 노드를 호출하며 중간에 부모 노드보다 큰 left node 혹은 작은 right node가 있는지 검사한다.

가장 밑에 있는 노드까지 검사하면서 부모 노드보다 큰 left node 또는 작은 right node가 발견되지 않을 경우 true를 반환하고, 발견될 경우 false를 반환한다.

이렇게 재귀적으로 검사한 값은 최종적으로 root node로 돌아가는데 이때 왼쪽 노드들 중에서 검사한 값이랑 오른쪽 노드들에서 검사한 값이 둘다 true일 경우에만 true를 반환하고 이외에는 false를 반환한다.