이진 탐색 트리 유효성 검사(Validating a Binary Search Tree)
References
아래 링크의 강의 중 Section 28. Validating a Binary Search Tree
의 내용을 추려 이번 글을 작성하였습니다.
The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy
Validating a Binary Search Tree
function validate(node, min = null, max = null) {
if (max !== null && node.data > max) {
return false;
}
if (min !== null && node.data < min) {
return false;
}
if (node.left && !validate(node.left, min, node.data)) {
return false;
}
if (node.right && !validate(node.right, node.data, max)) {
return false;
}
return true;
}
recursive function
과 if문
을 거치면서 입력값이 root
값을 기준으로 작다면 왼쪽에 위치하고, 크다면 오른쪽에 놓이게 한다. 여기서 왼쪽 트리를 탐색할 때는 탐색 중인 왼쪽 트리의 값이 max
값에 할당되어 그보다 작은 값만 왼쪽 트리에 저장되게끔 제한을 하고, 반대로 오른쪽은 min
값이 바뀌어 탐색 중인 오른쪽 트리의 값보다 큰 값만이 오른쪽에 저장되게끔 한다.
Author And Source
이 문제에 관하여(이진 탐색 트리 유효성 검사(Validating a Binary Search Tree)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mame-coder/이진-탐색-트리-유효성-검사Validating-a-Binary-Search-Tree저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)