4.5 BST 검증

문제 

주어진 이진트리가 이진 탐색 트리인지 확인하는 함수를 작성하라. 

 

접근법

1. 중위순회를 이용하여 배열의 원소를 저장해두고 이것이 정렬된 결과인지 확인한다. 

-> 중복된 값이 있을때 재대로 동작하지 않을 수 있다.

사실, 배열에 저장한다고 해도 바로 전의 원소와 그다음 원소만 사용하기 때문에 굳이 배열이 필요없음을 알 수 있다.

 

2. 마지막으로 검사했던 원소만 저장해두고 순회하며 그 다음 원소와 비교한다. 

 

last = float("Inf")
def chkBST(root):
    if root is None:
        return True

    if not chkBST(root.left) : return False
    if last != float("Int") and last >= root.data :
        return False
    last = root.data
    if not chkBST(root.right) : return False

    return True

def Solution(root):
    return chkBST(root)

 

3. 최소, 최대값 을 잡고 node의 값이 그 범위 안에 있는지 확인한다. 

def chkBST(root, min_, max_):
    if root is None : return Ture
    
    if (min_ is not None and min_ >= root.data) or (max_ is not None and max_ < root.data) : return False
    if not chkBST(root.left, min_, root.data) or not chkBST(root.right , root.data, max_) : return False
    return True

def Solution(root):
    return chkBST(root,None, None)