BST의 재귀 함수를 회귀가 아닌 것으로 변환하는 과정에서 인터뷰를 준비하는 중입니다. 지금까지 선주문, inorder, postorder, 검색, 삭제, 삽입 및 BST를 순환 연결된 목록으로 변환했습니다. 스택이나 대기열을 사용하여 높이를 얻고 BST인지 찾아내는 데 어려움이 있습니다. 모든 팁은 크게 감사하겠습니다. 나는 코드를 찾는 것이 아니라 코드의 논리를 찾고있다.트리의 높이를 재귀 적으로 구현하지 않는 의사 코드 및 isBST
처음에는 위와 같은 인터뷰를 준비하는 것이 좋습니다! 이 알고리즘으로 재미있게 놀고 싶습니다.
이진 트리가 BST인지 확인하는 작업부터 시작해 보겠습니다. 이 작업을 수행하는 한 가지 방법은 트리의 inorder walk를 수행하고 요소가 정렬 된 순서로 있는지 확인하는 것입니다. 트리가 BST 인 경우에만 true입니다. 트리 요소의 inorder 보행을 수행하는 코드를 이미 가지고 있기 때문에, inorder walk에서 나온 요소가 마지막 요소를 추적하여 정렬되는지 코드를 쉽게 적응할 수 있어야합니다 inorder walk를 수행 한 다음 생성 된 각 요소를 이전 요소와 비교합니다. 두 개가 고장난 경우 나무는 BST가 아닙니다.
트리의 높이를 결정하려면, 지금까지 나온 검색 (preorder, postorder, inorder) 중 하나를 취하여 각 지점에서 스택의 높이를 추적하는 것이 좋습니다 . 아이디어는 스택이 항상 어떤 노드에서 루트까지의 경로를 추적하므로 트리를 걷고 스택이 가장 깊게 보인 것을 기록 할 수 있습니다. 이 최대 깊이는 트리의 높이입니다.
희망이 도움이됩니다. 그리고 행운의 인터뷰와 함께 최고!
트리의 높이를 찾으려면 Morris 탐색 [O (n) 시간]을 사용할 수 있습니다.
유효한 BST인지 확인하려면 트리의 inorder walk를 수행하십시오. 요소를 배열로 이동하십시오. 어레이가 정렬되었는지 또는 BST의 유효성을 검증하지 않는지 점검하십시오.