Leetcode - 이진 검색 트리 유효성 검사(JavaScript 포함)

오늘은 Validate Binary Search Tree를 푸는 방법을 보여드리겠습니다.

문제는 다음과 같습니다.


이 문제에 대한 해결책을 설명하기 전에 BST(Binary Search Tree)가 무엇인지 간단히 살펴보겠습니다.

일반적으로 트리는 노드로 구성된 데이터 구조입니다. 각 트리에는 최상위 노드인 루트 노드와 0개 이상의 자식 노드가 있습니다. 문제에서 언급했듯이 이진 검색 트리는 각 노드가 최대 두 개의 자식을 가지며 다음 속성을 준수하는 트리 유형입니다.

노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키를 가진 노드만 포함됩니다.

노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가 있는 노드만 포함됩니다.

왼쪽 및 오른쪽 하위 트리도 모두 이진 검색 트리여야 합니다.

이 모든 것을 기반으로 BST의 모든 노드에는 최소값과 최대값이 있다고 말할 수 있습니다.



따라서 루트 노드에서 시작하여 주어진 트리 전체를 순회할 것입니다. 그런 다음 루트에서 아래로 이동하여 모든 하위 트리의 노드가 최소값과 최대값 사이에 래핑되어 있는지 확인하여 모든 하위 트리의 유효성을 검사합니다. null 값, 즉 하위 노드가 없는 리프 노드에 도달할 때까지 이 작업을 수행합니다.

이를 위해 추가 인수인 minValue 및 maxValue를 받는 도우미 메서드(validateBst)를 만들고 트리를 탐색할 때 값을 전달합니다. 노드의 왼쪽 하위 트리에서 도우미 메서드를 호출하면 최대값을 현재 노드의 값으로 변경합니다. 왼쪽 하위 트리에서 함수를 호출하면 최대값을 노드의 현재 값으로 변경합니다.

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

function validateBst(root, minValue, maxValue) {
    if(root == null) return true;
     if(root.val >= maxValue || root.val <= minValue) return false;
    return validateBst(root.right, root.val, maxValue) &&
            validateBst(root.left, minValue, root.val)
}