주어진 레벨 순서 순회에서 BST 구성

난이도 쉽게
자주 묻는 질문 아마존 Apple GE 헬스 케어 메트 라이프 Microsoft UHG 옵텀 큰소리로 말하다
이진 검색 트리 이진 트리 폭 우선 검색 나무 트리 순회조회수 26

주어진 레벨 순서 순회 이진 검색 트리의 경우 레벨 순서 순회가 주어진 ITS에서 이진 검색 트리 또는 BST를 구성하는 알고리즘을 작성합니다.

입력
levelOrder [] = {18, 12, 20, 8, 15, 25, 5, 9, 22, 31}
산출

주어진 레벨 순서 순회에서 BST 구성

순차 : 5 8 9 12 15 18 20 22 25 31

입력
levelOrder [] = {4, 2, 5, 1, 3, 6}
산출

주어진 레벨 순서 순회에서 BST 구성

순차 : 1 2 3 4

레벨 순서 순회에서 BST를 구성하기위한 알고리즘

레벨 순서 순회의 첫 번째 요소는 항상 이진 검색의 루트를 형성합니다. 나무. 다음 값은 값에 따라 왼쪽 노드 또는 오른쪽 노드를 형성 할 수 있습니다.

다음 노드가 루트보다 작 으면 루트의 왼쪽에 삽입됩니다. 그렇지 않으면 오른쪽에 삽입됩니다.
아이디어는 다음과 같이 BST의 루트가 null이면 현재 요소가 루트보다 작게 형성되어 루트의 왼쪽 하위 트리의 적절한 위치에 삽입하고 그렇지 않으면 오른쪽 하위 트리에 부적절한 위치에 삽입합니다. 뿌리의.

  1. BST의 루트를 null로 초기화합니다. 레벨 순서 순회에 요소가 없으면 루트를 반환합니다.
  2. levelOrder 배열의 모든 요소에 대해 3, 4, 5 단계를 반복합니다.
  3. 루트가 null이면 현재 요소를 루트로 만듭니다.
  4. 그렇지 않으면 현재 요소가 루트보다 작은 경우 3 단계로 이동하면 루트가 root.left가되고 요소는 동일하게 유지됩니다.
  5. 그렇지 않으면 현재 요소가 루트보다 크면 3 단계로 이동하여 루트가 root.right가되고 요소는 동일하게 유지됩니다.
  6. 루트를 반환합니다.

레벨 순서 순회에서 BST를 구성하기위한 JAVA 코드

public class ConstructBSTFromItsGivenLevelOrderTraversal {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // function to print in order traversal of a binary tree
    private static void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    private static Node attachNode(Node root, int value) {
        // if root is null, make the current element as root
        if (root == null) {
            root = new Node(value);
            return root;
        }

        // if element is less than root
        if (value < root.data) {
            // attach it to left subtree
            root.left = attachNode(root.left, value);
        } else {
            // attach it to right subtree
            root.right = attachNode(root.right, value);
        }

        // return root
        return root;
    }

    private static Node formBST(int[] levelOrder) {
        // initialize root as null
        Node root = null;

        // for each element attach the node to required position in the BST
        for (int i = 0; i < levelOrder.length; i++) {
            // Step 3 to 5
            root = attachNode(root, levelOrder[i]);
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int levelOrder1[] = new int[] {18, 12, 20, 8, 15, 25, 5, 9, 22, 31};
        Node root1 = formBST(levelOrder1);
        inorder(root1);
        System.out.println();

        // Example 2
        int levelOrder2[] = new int[] {4, 2, 5, 1, 3, 6};
        Node root2 = formBST(levelOrder2);
        inorder(root2);
        System.out.println();
    }
}
5 8 9 12 15 18 20 22 25 31 
1 2 3 4 5 6

레벨 순서 순회에서 BST를 구성하기위한 C ++ 코드

#include <iostream> 
#include<vector> 
#include<queue> 
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; 
    } 
}; 

// function to print the in-order traversal of a binary tree 
void inOrder(Node *root) { 
    if (root != NULL) { 
        inOrder(root->left); 
        cout<<root->data<<" "; 
        inOrder(root->right); 
    } 
} 

Node* attachNode(Node *root, int value) {
    // if root is null, make the current element as root
    if (root == NULL) {
        root = new Node(value);
        return root;
    }
    
    // if element is less than root
    if (value < root->data) {
        // attach it to left subtree
        root->left = attachNode(root->left, value);
    } else {
        // attach it to right subtree
        root->right = attachNode(root->right, value);
    }
    
    // return root
    return root;
}

Node* formBST(int *levelOrder, int n) {
    // initialize root as null
    Node *root = NULL;
    
    // for each element attach the node to required position in the BST
    for (int i = 0; i < n; i++) {
        // Step 3 to 5
        root = attachNode(root, levelOrder[i]);
    }
    
    // return root
    return root;
}

int main() { 
    // Example 1
    int levelOrder1[] = {18, 12, 20, 8, 15, 25, 5, 9, 22, 31};
    Node *root1 = formBST(levelOrder1, sizeof(levelOrder1) / sizeof(levelOrder1[0]));
    inOrder(root1);
    cout<<endl;

    // Example 2
    int levelOrder2[] = {4, 2, 5, 1, 3, 6};
    Node *root2 = formBST(levelOrder2, sizeof(levelOrder2) / sizeof(levelOrder2[0]));
    inOrder(root2);
    cout<<endl;
    
    return 0; 
}
5 8 9 12 15 18 20 22 25 31 
1 2 3 4 5 6

복잡성 분석

시간 복잡성 = 의 위에2)
공간 복잡성 = O (N), 재귀로 인해
여기서 n은 레벨 순서의 총 요소 수입니다. 정렬.

레퍼런스 1     참조 2

Translate »