drop-of-water

문제 링크

조건

  • 노드의 갯수 [1, 10^4].
  • -2^31 <= Node.val <= 2^31 - 1
  • valid BST 조건 -> 노드의 왼쪽 subtree는 node val 보다 작은 값 -> 노드의 오른쪽 subtree는 node val 보다 큰 값 -> 노드의 왼쪽, 오른쪽 subtree도 바이너리 서치 트리여야함

입력값

  • root = 바이너리 서치 트리의 루트

출력값

  • bool = 바이너리 서치 트리인지 참/거짓 값

풀이과정

  • 현재 노드의 값이 min(이전 값 or 왼쪽 subtree의 최대값)과 max (이전 값 or 오른쪽 subtree의 최소값) 사이의 값이 아닌 경우 바이너리 서치 트리가 아님

코드

const isValidBST = (root) => {
  if (root === null) return false;
  return isBST(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);

  function isBST(r, min, max) {
    if (r === null) return true;
    if (r.val <= min || r.val >= max) return false;

    return isBST(r.left, min, Math.min(max, r.val)) && isBST(r.right, Math.max(min, r.val), max);
  }
};

😊