크기 n의 주어진 배열이 n 레벨의 BST를 나타낼 수 있는지 확인하십시오.


난이도 쉽게
자주 묻는 질문 아마존 훌루 인텔 주니퍼 네트웍스 Microsoft Robinhood 큰소리로 말하다
배열 이진 검색 트리 이진 트리 나무

문제 정책

n 개의 요소가있는 배열이 주어지면 크기 n의 배열이 n 레벨의 BST를 나타낼 수 있는지 확인하십시오. 이는 이진 검색 트리가 이들을 사용하여 구성되었는지 확인하는 것입니다. n 요소는 다음의 BST를 나타낼 수 있습니다. n 레벨.

arr[] = {10, 8, 6, 9, 3}
false

설명 : 8과 9는 BST에서 같은 레벨에 배치됩니다. 우리는 n 레벨의 BST를 얻을 수 없습니다.

크기 n의 주어진 배열이 n 레벨의 BST를 나타낼 수 있는지 확인하십시오.

arr[] = {18, 12, 6, 9, 7}
true

설명 : 여기에서 위의 그림과 같이 동일한 레벨에있는 두 요소가 없습니다. 따라서 우리는 n 크기의 BST를 남깁니다.

 

접근

방법 1 (트리를 구성하여)

위의 문제를 해결하는 방법 중 하나는 현재 노드의 왼쪽에 현재 노드보다 작은 값을, 현재 노드의 오른쪽에 현재 노드보다 큰 값을 삽입하여 주어진 배열에서 n 레벨의 트리를 구성하는 것입니다.
트리를 구성한 후 트리가 바이너리 검색 트리인지 아닌지 확인합니다. 이진 검색 트리이면 출력이 참이고 그렇지 않으면 출력이 거짓입니다. 이 참이면 n 크기의 주어진 배열이 n 레벨의 BST를 나타낼 수 있는지 여부를 확인하고 가능하다는 것을 발견했습니다.

1. Initialize root as the first element of the given array. Also initialize temp as root.
2. Traverse the given array starting from index 1(0-based indexing), if the current element is less than temp's value insert it to the left of temp and make temp as left of temp, else insert the current element to the right of temp and make temp as right of temp.
3. After building the tree with n levels using step 2, check if the constructed tree is BST or not. If it is BST return true, else return false.

복잡성 분석

시간 복잡성 = 의 위에), 크기의 전체 입력을 통과하고 있기 때문에 n.
공간 복잡성 = 오), 여기서는 입력 배열의 각 요소에 대한 노드를 생성합니다. 따라서 총 n 개의 노드를 만드는 것은 선형 공간 복잡성에 기여합니다.
여기서 n은 배열의 요소 수이고 h는 BST의 높이입니다.이 경우 h 다음과 같다 n.

JAVA 코드

import java.util.*;
import java.lang.*;
import java.io.*;
 
class CheckGivenArrayOfSizenCanRepresentBSTOfnLevelsOrNot {
    // class to represent the node of a binary tree
    static class Node {
        int data;
        Node left, right;
        public Node(int data) {
            this.data = data;
        }
    }
    // function to check if a tree is BST or not
    private static boolean isBST(Node root, int min, int max) {
        if (root == null) {
            return true;
        }
        return (root.data < max && root.data > min) &&
                isBST(root.left, min, root.data) &&
                isBST(root.right, root.data, max);
    }
    private static Node constructNLevelTree(int[] arr) {
        // initialize root as first element of array
        Node root = new Node(arr[0]);
        // initialize temp as root
        Node temp = root;
        // traverse the array from index 1
        for (int i = 1; i < arr.length; i++) {
            // if current element is less than temp, make temp's left as current element
            // and temp as temp's left
            if (arr[i] < temp.data) {
                temp.left = new Node(arr[i]);
                temp = temp.left;
            }
            // else, make temp's right as current element
            // and temp as temp's right
            else {
                temp.right = new Node(arr[i]);
                temp = temp.right;
            }
        }
        // return the root of tree formed
        return root;
    }
    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[] {10, 8, 6, 9, 3};
        Node root1 = constructNLevelTree(arr1);
        System.out.println(isBST(root1, Integer.MIN_VALUE, Integer.MAX_VALUE));
        // Example 2
        int arr2[] = new int[] {18, 12, 6, 9, 7};
        Node root2 = constructNLevelTree(arr2);
        System.out.println(isBST(root2, Integer.MIN_VALUE, Integer.MAX_VALUE));
    }
}

 

false
true

C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

bool isBST(Node *root, int min, int max) {
    if (root == NULL) {
        return true;
    }
    
    return (root->data < max && root->data > min && 
                isBST(root->left, min, root->data) && 
                isBST(root->right, root->data, max));
}

Node* constructNLevelTree(int *arr, int n) {
    // initialize root as first element of array
    Node *root = new Node(arr[0]);
    // initialize temp as root
    Node *temp = root;
    
    // traverse the array from index 1
    for (int i = 1; i < n; i++) {
        // if current element is less than temp, make temp's left as current element
        // and temp as temp's left
        if (arr[i] < temp->data) {
            temp->left = new Node(arr[i]);
            temp = temp->left;
        } 
        // else, make temp's right as current element
        // and temp as temp's right
        else {
            temp->right = new Node(arr[i]);
            temp = temp->right;
        }
    }
    
    // return the root of tree formed
    return root;
}

int main() {
    // Example 1
    int arr1[] = {10, 8, 6, 9, 3};
    Node *root1 = constructNLevelTree(arr1, sizeof(arr1) / sizeof(arr1[0]));
    if (isBST(root1, INT_MIN, INT_MAX)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    int arr2[] = {18, 12, 6, 9, 7};
    Node *root2 = constructNLevelTree(arr2, sizeof(arr2) / sizeof(arr2[0]));
    if (isBST(root2, INT_MIN, INT_MAX)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
false
true

방법 2 (트리를 생성하지 않음)

크기 n의 주어진 배열이 n 레벨의 BST를 나타낼 수 있는지 확인하거나 일정한 공간 복잡성으로 문제를 해결할 수 있습니다. 아이디어는 다음 요소가 새 수준에 표시 될 최소값과 최대 값의 조건을 보장하는 최소 및 최대 두 개의 변수를 유지하는 것입니다. 즉, 요소는 최소와 최대 사이에 있어야 새 레벨에 표시됩니다. 그렇지 않으면 트리의 기존 레벨에 삽입됩니다.

1. Initialize min as -infinity and max as infinity.
2. Traverse the given array from index 1(0-based indexing).
3. If the current element is greater than prev element, and also it lies in the range min and max, then update min as prev element.
4. Else if the current element is smaller than prev element and it lies in the range min and max, then update max as prev element.
5. If none of the conditions in step 3 and step 4 is true, return false.
6. At the end of traversal return true.

복잡성 분석

시간 복잡성 = 의 위에), 우리는 크기 n의 전체 입력을 순회하고 있기 때문입니다.
공간 복잡성 = O (1), 각 요소에 대한 노드를 생성하지 않기 때문입니다. 그리고 특정 수의 변수 만 사용했으며 상수 공간 솔루션이 있습니다.
여기서 n은 배열의 요소 수입니다.

JAVA 코드

import java.util.*;
import java.lang.*;
import java.io.*;
 
class CheckGivenArrayOfSizenCanRepresentBSTOfnLevelsOrNot {
    private static boolean canRepresent(int[] arr) {
        // initialise min as -infinity and max as infinity
        int min = Integer.MIN_VALUE, max = Integer.MAX_VALUE;
        // traverse the array from index 1
        for (int i = 1; i < arr.length; i++) {
            // if current element is greater than prev and lies in the
            // range min and max, update min as prev
            if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {
                min = arr[i - 1];
            }
            // else if current element is less than prev and lies in the
            // range min and max, update max as prev
            else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max) {
                max = arr[i - 1];
            }
            // in all other cases return false
            else {
                return false;
            }
        }
        // at the end of the traversal return true
        return true;
    }
    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[] {10, 8, 6, 9, 3};
        System.out.println(canRepresent(arr1));
        // Example 2
        int arr2[] = new int[] {18, 12, 6, 9, 7};
        System.out.println(canRepresent(arr2));
    }
}
false
true

C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 

bool canRepresent(int *arr, int n) {
    // initialise min as -infinity and max as infinity
    int min = INT_MIN, max = INT_MAX;
    
    // traverse the array from index 1
    for (int i = 0; i < n; i++) {
        // if current element is greater than prev and lies in the
        // range min and max, update min as prev
        if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {
            min = arr[i - 1];
        }
        // else if current element is less than prev and lies in the
        // range min and max, update max as prev
        else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max) {
            max = arr[i - 1];
        }
        // in all other cases return false
        else {
            return false;
        }
    }
    
    // at the end of the traversal return true
    return true;
}

int main() {
    // Example 1
    int arr1[] = {10, 8, 6, 9, 3};
    if (canRepresent(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    int arr2[] = {18, 12, 6, 9, 7};
    if (canRepresent(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
false
true