[LeetCode] 98. Validate Binary Search Tree

문제 출처: https://leetcode.com/problems/validate-binary-search-tree/

Validate Binary Search Tree - LeetCode

문제

이진 트리의 루트가 주어지면, 트리가 이진 탐색 트리(BST)인지 아닌지 판별하라.

 

유효한 BST는 다음 규칙을 따른다:

 

한 노드의 왼쪽 서브트리는 해당 노드의 키 값보다 작은 키를 가져야 한다. 한 노드의 오른쪽 서브트리는 해당 노드의 키보다 큰 값만을 가져야 한다. 왼쪽과 오른쪽 서브트리 또한 이진 탐색 트리여야 한다.

예제

Input: root = [5,1,4,null,null,3,6]
Output: false

Explanation: The root node's value is 5 but its right child's value is 4.

풀이

가장 먼저 떠올릴 수 있는 방법은 트리를 중위순회 방식으로 탐색하며 값을 배열로 저장하고, 해당 배열이 오름차순으로 정렬된 배열인지 체크하는 것이다

function isValidBST(root) {
    let arr = treeToArray(root, []);

    if (let i = 0; i < arr.length; i++) {
        if (arr[i] > arr[i+1]) { return false; }
    }

    return true;
}

function treeToArray(root, result) {
    if (root.left != null) {
        treeToArray(root.left, result);
    }

    result.push(root.val);

    if (root.right != null) {
        treeToArray(root.right, result);
    }

    return result;
}

이 코드에서 한가지 생각할 수 있는 개선점은 중위순회 시 접근하는 노드의 순서가 배열을 통해 접근하는 값과 동일한 순서라는 것이다. 즉, 중위순회만 이용하여 BST 체크를 할 수 있다는 것이다. 다음 코드를 살펴보자.

function isValidBST(root) {
    let lastVal = null;

    function checkBST(root) {
        if (root == null) return true;

        if (!checkBST(root.left)) return false;

        if (lastVal != null && root.val < lastVal) return false;
        lastVal = root.val;

        if (!checkBST(root.right)) return false;

        return true;
    }

    return checkBST(root);
}

마지막에 방문했던 노드 값을 기억하는 변수(lastVal)을 이용하였고, 왼쪽트리 탐색 이후에 lastVal과의 현재 노드의 값 비교를 통해 BST 여부를 체크하도록 하였다.

 

Github: 98.js

opwe37/Algorithm-Study