올바른 이진 탐색 트리인지 확인하기

문제는 아니고 이론이다. 특정한 트리가 주어졌을 때 이 트리가 이진탐색 트리의 조건에 만족하는지 만족하지 못하는지 체크하는 문제이다. 이진 탐색 트리를 만족하기 위해서는 부모의 노드 오른쪽에는 큰 값 왼쪽에는 작은 값이 위치하는 것을 체크해주면 된다. 하지만 이를 하나하나씩 다 체크해주면 확인하기에는 시간복잡도 부분에서 오래걸리게 된다. 따라서 O(n)만에 해결하는 방법을 작성해보려고 한다. 우선 아래 그림을 보자 해당 노드의 최대 값과 최소 값을 지정한 후 이 사이에 있다면 참이고 그 반대면 거짓이 된다. 참과 거짓을 밝히는 if문은 아래와 같다. if(minValue value) true; if(minValue > value || maxValue value valu..

2021.01.19