유효한 BST 확인

이진 트리의 루트가 주어지면 유효한 이진 검색 트리(BST)인지 확인합니다.

유효한 BST는 다음과 같이 정의됩니다.

노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키를 가진 노드만 포함됩니다.
노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가 있는 노드만 포함됩니다.
왼쪽 및 오른쪽 하위 트리도 모두 이진 검색 트리여야 합니다.

예 1:

입력: 루트 = [2,1,3]
출력: 참

접근법 1: 최대 및 최소 범위 두 값 유지

var isValidBST = function (root) {
  return validate(root, -Infinity, Infinity);
};

var validate = function (node, lower, upper) {
  if (node == null) {
    // empty node or empty tree
    return true;
  }

  if (lower < node.val && node.val < upper) {
    // check if all tree nodes follow BST rule
    return (
      validate(node.left, lower, node.val) &&
      validate(node.right, node.val, upper)
    );
  } else {
    // early reject when we find violation
    return false;
  }
};

접근 방식 2: 순서대로 순회 수행 및 정렬된 배열로 배열 검사.

var isValidBST = function (root) {
  function inOrder(node) {
    if (!node) return [];
    return [...inOrder(node.left), node.val, ...inOrder(node.right)];
  }

  const sortedArr = inOrder(root);

  for (let i = 0; i < sortedArr.length; i++) {
    if (sortedArr[i + 1] <= sortedArr[i]) return false;
  }
  return true;
};

접근법 3: InOrder Traversal 수행 및 비교를 수행하기 위해 하나의 Min 포인터 유지

var isValidBST = function (root) {
  let previous = -Infinity;

  function checkInOrder(root) {
    if (root === null) {
      return null;
    }
    if (checkInOrder(root.left) === false) {
      return false;
    }
    if (root.val <= previous) {
      return false;
    }
    previous = root.val;
    return checkInOrder(root.right);
  }

  return checkInOrder(root);
};