LeetCode / Binary Search Tree / 98번 / Validate Binary Search Tree / JS

< 문제 바로가기 >

Validate Binary Search Tree - LeetCode

 

< 문제 간단설명 >

주어진 Tree가 유효한 BST(Binary Search Tree)인지 확인해서 boolean 값을 반환하는 문제이다.

BST가 되기 위한 조건은 다음과 같다.

• 왼쪽 하위트리는 모두 부모노드의 값보다 작아야 한다.
• 오른쪽 하위트리는 모두 부모노드의 값보다 커야 한다.
• 왼쪽, 오른쪽 하위트리 모두 또한 BST를 이루어야 한다.(위의 2개의 조건들이 모두 맞아야 한다)

 

/**
 * 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) {
    const validate = (min, root, max) => {
        if(!root) return true;

        if(root.val <= min || root.val >= max) return false;

        let leftValidation = validate(min, root.left, root.val);
        let rightValidation = validate(root.val, root.right, max);

        return leftValidation && rightValidation;
    }

    return validate(-Infinity, root, Infinity);
};

---

처음에 최소값을 -Infinity, 최대값을 Infinity로 설정을 해준다.

그리고 나서 재귀를 돌게 되는데, 재귀의 인자는 (최소값, root, 최대값)이다.

 

왼쪽 서브트리는 왼쪽 서브트리의 root가 현재 root의 값보다 작아야한다. 따라서 인자로 (최소값, root.left, root.val)을 계속 넘겨주면서 재귀를 수행하게 된다.

오른쪽 서브트리는 오른쪽 서브트리의 root가 현재 root의 값보다 커야한다. 따라서 인자로 (root.val, root.right, 최대값)을 계속 넘겨주면서 재귀를 수행하게 된다.

 

계속 재귀를 진행하면서 root가 null이라면, 즉 Tree의 끝까지 다다랐다면 종료조건에 걸리지 않았다는 것이므로 true를 반환하게 된다.

 

false를 반환하는 조건은 현재 root의 값이 최소값보다 작거나 최대값보다 크게되면 BST를 만족하지 않으므로 false를 반환하게 된다.