← 14주차 · 트리와 이진 트리
보통트리DFS재귀

이진 탐색 트리 유효성 검사

이진 트리의 루트 root가 주어져요. 이 트리가 이진 탐색 트리(BST)이면 true, 아니면 false를 반환해요.

이진 탐색 트리는 모든 노드에 대해 왼쪽 서브트리의 모든 값이 자기 값보다 작고, 오른쪽 서브트리의 모든 값이 자기 값보다 커야 해요. 바로 아래 두 자식만 보는 것으로는 부족해요 — 손자 이하도 조건을 지켜야 해요.

값은 모두 서로 다르다고 가정해요. 빈 트리는 유효한 BST예요.

트리는 레벨 순서 배열로 주어져요. null은 자식이 없다는 뜻이고, 채점기가 이 배열을 노드로 바꿔서 root로 넘겨줘요. 노드는 val, left, right를 가지며, 새 노드가 필요하면 TreeNode로 만들 수 있어요.

예시

예시 1
입력
root = [2, 1, 3]
출력
true
예시 2
입력
root = [5, 1, 4, null, null, 3, 6]
출력
false
설명
4는 5의 오른쪽에 있어서 5보다 커야 하는데 그렇지 않아요. 부모인 4만 보면 3과 6은 올바르지만, 조상인 5까지 따지면 어긋나요.
예시 3
입력
root = []
출력
true

제한 사항

  • 노드 개수는 0개 이상 10,000개 이하예요.
  • -100,000 ≤ node.val ≤ 100,000
  • 모든 값은 서로 달라요.
노드마다 '이 값이 들어갈 수 있는 범위'를 물려주세요. 왼쪽으로 내려가면 상한이 부모 값으로 좁혀지고, 오른쪽으로 내려가면 하한이 부모 값으로 좁혀져요. 중위 순회 결과가 오름차순인지 보는 방법도 있어요.
javascript
function isValidBST(root) {
  const check = (node, low, high) => {
    if (node === null) return true;
    if (low !== null && node.val <= low) return false;
    if (high !== null && node.val >= high) return false;
    return check(node.left, low, node.val) && check(node.right, node.val, high);
  };
  return check(root, null, null);
}
이전 문제트리 뒤집기
다음 문제경로 존재 판별
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.