주어진 배열이 이진 검색 트리의 후행 순회를 나타내는 지 확인하는 방법?

Question

주어진 배열이 있고 그것이 BST의 순차적 순회를 나타내는 지 알아야합니다. (예 : 질문이 순서가 아닌 순서로 된 경우 배열의 시간이 o (n)으로 정렬되어 있는지 확인하기 만하면됩니다.

Answer 1

빠른 정당성 검사 : 배열의 마지막 항목이 아닌 경우 루트 노드는 post-order traversal의 결과가 아닙니다. 마찬가지로 선주문 탐색이 수행 된 경우 배열의 첫 번째 항목이 루트입니다.

Answer 2

후행 탐색은 {LEFT Subtree} {Right Subtree} {ROOT}에 의해 수행됩니다. 따라서 여기에서 아이디어는 오른쪽 끝에서 배열을 횡단하기 시작하는 것입니다. 배열의 마지막 요소는 루트이고, 오른쪽에서 왼쪽으로 작은 요소를 만나면 왼쪽 하위 트리로 시작하도록 경계를 표시하고 BST에는이 인덱스의 더 큰 요소가 없습니다. 이것은 각 하위 트리에 적용됩니다 . C++의 알고리즘은 다음과 같이 간다 -

bool isBST(int arr[], int n){ 

//Set root to the max integer value. 
int root = INT_MAX; 

//Stack used to keep track of current subtree 
std::stack<int>s; 

//Start at the end of the array because Postorder traversal is 
// <L><R><D> 
for (int i = n-1; i>=0; i--) { 
    //False if any larger number in the left subtree 
    if (arr[i]> root) { 
     return false; 
    } 

    //Reset the root for boundary of every subtree, 
    //when current item is smaller than top, 
    //that means we are starting with left subtree of this root 
    while (!s.empty() && arr[i] < s.top()) { 
     root = s.top(); 
     s.pop(); 
    } 
    //Keep pushing the elements otherwise 
    s.push(arr[i]); 
    } 
    return true; 

}