[Leetcode] 98. Validate Binary Search Tree - JS

https://leetcode.com/problems/validate-binary-search-tree/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
이진트리의 루트가 주어질 때, 유효한 BST(이진검색트리)인지 확인하라.
- 왼쪽 하위 트리에는 노드의 값보다 작은 값을 가진 노드들만 포함한다.
- 오른쪽 하위 트리에는 노드의 값보다 큰 값을 가진 노드들만 포함한다.
- 왼쪽, 오른쪽 모두 BST여야 한다.

제한조건
--------------------
- 노드의 갯수는 1 ~ 10^4개이다.
- -2^31 <= node.val <= 2^31 - 1

 

2. 접근 방법

접근방법
--------------------
재귀함수에 노드와 노드 값의 최대, 최소값을 파라미터로 같이 전달한다.
이때, 최대 최소값은 전달하는 node가 왼쪽 자식인지, 오른쪽 자식인지에 따라 다르게 설정한다.
왼쪽 자식 노드에게는 현재 노드의 값이 최댓값으로 전달해야하고
오른쪽 자식 노드에게는 현재 노드의 값이 최솟값으로 전달해야한다.

만약, 자식 노드값이 최대값보다 크거나 같거나 혹은 최소값보다 작거나 같으면.. 유효한 이진 검색 트리가 아니다.

 

 

3. 코드

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

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

        return (validate(node.left, min, node.val) 
        && validate(node.right, node.val, max))
    }
    return validate(root, -Infinity, Infinity)
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n) 

- 공간복잡도: O(1)

 

이진 검색 트리가 직계 부모와의 대소 관계만 비교하는 건 줄 알았는데, 최상위 부모를 기준으로 왼쪽, 오른쪽 하위 트리의 구성요소 모두 만족해야한다는 것을 알게 되었다.

각 노드마다 최대, 최소값을 파라미터로 전달하여 자신의 부모 노드와 값을 비교할 수 있도록 접근하였다.

 

claude 와 함께 공부하니 이해가 잘된다. 하지만 이는 내가 직접 푼 것이 아니므로 남에게 설명할 수 있을 정도로 반복해서 풀어봐야한다.