← 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);
}
이전 문제트리 뒤집기
다음 문제경로 존재 판별
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.