주어진 선주문 순회에서 BST 구성-TutorialCup

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

Twitter Facebook 링크드인 버퍼 레딧 텀블러

이진 검색 트리 (BST)의 사전 주문 순회가 주어지면 주어진 BST를 구성하는 알고리즘을 작성하십시오. 선주문 순회.

차례

예

입력
선주문 [] = {7, 5, 3, 6, 9}
산출

핀

순서 : 3 5 6 7 9

입력
선주문 [] = {12, 6, 1, 35, 20}
산출

핀

순서 : 1 6 12 20 35

순진한 접근

사전 주문 순회에서 첫 번째 요소는 항상 나무 나머지 요소는 왼쪽 및 오른쪽 하위 트리의 일부입니다. 트리가 BST이므로 루트보다 작은 모든 요소가 왼쪽 하위 트리에 존재하고 루트보다 큰 요소가 오른쪽 하위 트리에 존재합니다.

그래서 우리는 주어진 배열을 순회하고 루트보다 큰 첫 번째 요소를 찾습니다. 이제이 요소 (루트 제외) 앞의 요소는 왼쪽 하위 트리의 사전 주문 순회이며이 요소 (포함) 이후의 요소는 오른쪽 하위 트리의 사전 주문 순회입니다.

따라서 첫 번째 요소는 BST의 루트를 형성하고 인덱스 1에서 (i – 1)까지의 요소는 왼쪽 하위 트리를 형성하고 인덱스 i에서 (n – 1)까지의 요소는 오른쪽 하위 트리를 형성합니다.

createBST (선주문, 저가, 고가)

배열의 첫 번째 요소 (preOrder [low])는 BST의 루트입니다. low가 high와 같으면 root를 반환합니다.
인덱스 low + 1 (0 기반 인덱싱)에서 high로 배열을 순회하고 루트보다 큰 첫 번째 요소를 찾고 인덱스를 i로 둡니다.
인덱스 (low + 1)부터 (i – 1)까지의 요소에 대해이 메서드를 재귀 적으로 호출하고 루트의 왼쪽에 형성된 BST를 할당합니다.
인덱스 i에서 high까지의 요소에 대해이 메서드를 재귀 적으로 호출하고 루트 오른쪽에 형성된 BST를 할당합니다.
루트를 반환합니다.

시간 복잡성 = 의 위에²)
공간 복잡성 = O (N), 재귀로 인해
여기서 n은 주어진 선주문 배열의 크기입니다.

주어진 선주문 순회에서 생성 BST에 대한 JAVA 코드

public class ConstructBSTFromGivenPreorderTraversal {
    // class representing Node of BST
    static class Node {
        int data;
        Node left, right;

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

    // function to print inorder 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 createBST(int[] preOrder, int low, int high) {
        // if there is only 1 node in the tree, this is root, return it
        if (low == high) {
            return new Node(preOrder[low]);
        }

        // the first node is the root of the BST
        Node root = new Node(preOrder[low]);

        // find the index of first element greater than root
        int index = -1;
        for (int i = low + 1; i <= high; i++) {
            if (preOrder[i] > preOrder[low]) {
                index = i;
                break;
            }
        }

        // if all the elements are smaller than root, they forms the left subtree
        // and right subtree is null
        if (index == -1) {
            root.left = createBST(preOrder, low + 1, high);
            root.right = null;
        }
        // else elements from index (low + 1) to (index - 1) forms  the left subtree
        // and elements from index 'index' to high forms the right subtree
        else {
            root.left = createBST(preOrder, low + 1, index - 1);
            root.right = createBST(preOrder, index, high);
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int preOrder1[] = new int[] {7, 5, 3, 6, 9};
        Node root1 = createBST(preOrder1, 0, preOrder1.length - 1);
        inorder(root1);
        System.out.println();

        // Example 2
        int preOrder2[] = new int[] {12, 6, 1, 35, 20};
        Node root2 = createBST(preOrder2, 0, preOrder2.length - 1);
        inorder(root2);
        System.out.println();
    }
}

3 5 6 7 9 
1 6 12 20 35

지정된 선주문 순회에서 생성 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* createBST(int *preOrder, int low, int high) {
    // if there is only 1 node in the tree, this is root, return it
    if (low == high) {
        return new Node(preOrder[low]);
    }
    
    // the first node is the root of the BST
    Node *root = new Node(preOrder[low]);
    
    // find the index of first element greater than root
    int index = -1;
    for (int i = low + 1; i <=high; i++) {
        if (preOrder[i] > preOrder[low]) {
            index = i;
            break;
        }
    }
    
    // if all the elements are smaller than root, they forms the left subtree
    // and right subtree is null
    if (index == -1) {
        root->left = createBST(preOrder, low + 1, high);
        root->right = NULL;
    }
    // else elements from index (low + 1) to (index - 1) forms  the left subtree
    // and elements from index 'index' to high forms the right subtree
    else {
        root->left = createBST(preOrder, low + 1, index - 1);
        root->right = createBST(preOrder, index, high);
    }
    
    // return root
    return root;
}

int main() {
    // Example 1
    int preOrder1[] = {7, 5, 3, 6, 9};
    Node *root1 = createBST(preOrder1, 0, (sizeof(preOrder1) / sizeof(preOrder1[0])) - 1);
    inOrder(root1);
    cout<<endl;

    // Example 2
    int preOrder2[] = {12, 6, 1, 35, 20};
    Node *root2 = createBST(preOrder2, 0, (sizeof(preOrder2) / sizeof(preOrder2[0])) - 1);
    inOrder(root2);
    cout<<endl;
    
    return 0;
}

3 5 6 7 9 
1 6 12 20 35

최적의 접근 방식

주어진 선주문 순회에서 BST를 구성하는 재귀 적 방법

여기서 최적의 아이디어는 범위 트릭을 사용하는 것입니다. 즉, 모든 노드에 대한 범위를 설정하면 범위에 포함 된 노드가 트리의 루트를 형성합니다.

처음에는 범위가 -infinity (min) 및 + infinity (max)이므로 첫 번째 근이 범위에 들어와 근을 형성합니다. 그런 다음 왼쪽 자식 (업데이트 된 범위는 최소에서 루트 값까지)과 오른쪽 자식 (업데이트 된 범위는 루트 값에서 최대까지)에 대해 동일한 메서드를 호출합니다.

createBST (최소, 최대)

currIndex (globally defined)에있는 요소의 값이 min과 max (둘 다 포함되지 않음) 사이에 있으면 루트를 형성합니다. 메모리를 할당하고 root라는 새 노드를 만듭니다. 그렇지 않으면 4 단계로 이동합니다.
currIndex를 증가시키고이 메소드를 재귀 적으로 호출하여 ConstructBST (min, root 's value)와 같이 왼쪽 하위 트리를 형성합니다.
재귀 적으로이 메서드를 호출하여 ConstructBST (root 's value, max)와 같이 오른쪽 하위 트리를 형성합니다.
루트를 반환합니다.

시간 복잡성 = O (N)
공간 복잡성 = O (N)
여기서 n은 사전 주문 배열의 크기입니다.

주어진 선주문 순회에서 생성 BST에 대한 JAVA 코드

public class ConstructBSTFromGivenPreorderTraversal {
    // class representing Node of BST
    static class Node {
        int data;
        Node left, right;

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

    // globally defined currIndex integer
    private static int currIndex = 0;

    // function to print inorder 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 createBST(int[] preOrder, int min, int max) {
        if (currIndex >= preOrder.length) {
            return null;
        }

        Node root = null;

        // if current element is in between min and max
        if (preOrder[currIndex] > min && preOrder[currIndex] < max) {
            // allocate memory for it
            root = new Node(preOrder[currIndex]);
            // increment currIndex
            currIndex++;
            // make left of root as createBST(min, root's data)
            root.left = createBST(preOrder, min, root.data);
            // make right of root as createBST(root's data, max)
            root.right = createBST(preOrder, root.data, max);
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int preOrder1[] = new int[] {7, 5, 3, 6, 9};
        currIndex = 0;
        Node root1 = createBST(preOrder1, Integer.MIN_VALUE, Integer.MAX_VALUE);
        inorder(root1);
        System.out.println();

        // Example 2
        int preOrder2[] = new int[] {12, 6, 1, 35, 20};
        currIndex = 0;
        Node root2 = createBST(preOrder2, Integer.MIN_VALUE, Integer.MAX_VALUE);
        inorder(root2);
        System.out.println();
    }
}

3 5 6 7 9 
1 6 12 20 35

지정된 선주문 순회에서 생성 BST를위한 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; 
    } 
}; 

// globally defined currIndex integer
int currIndex = 0;

// 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* createBST(int *preOrder, int min, int max, int n) {
    if (currIndex >= n) {
        return NULL;
    }
    
    Node *root = NULL;
    
    // if current element is in between min and max
    if (preOrder[currIndex] > min && preOrder[currIndex] < max) {
        // allocate memory for it
        root = new Node(preOrder[currIndex]);
        // increment currIndex
        currIndex++;
        // make left of root as createBST(min, root's data)
        root->left = createBST(preOrder, min, root->data, n);
        // make right of root as createBST(root's data, max)
        root->right = createBST(preOrder, root->data, max, n);
    }
    
    // return root
    return root;
}

int main() {
    // Example 1
    int preOrder1[] = {7, 5, 3, 6, 9};
    currIndex = 0;
    Node *root1 = createBST(preOrder1, INT_MIN, INT_MAX, sizeof(preOrder1) / sizeof(preOrder1[0]));
    inOrder(root1);
    cout<<endl;

    // Example 2
    int preOrder2[] = {12, 6, 1, 35, 20};
    currIndex = 0;
    Node *root2 = createBST(preOrder2, INT_MIN, INT_MAX, sizeof(preOrder2) / sizeof(preOrder2[0]));
    inOrder(root2);
    cout<<endl;
    
    return 0;
}

3 5 6 7 9 
1 6 12 20 35

반복 방법

여기서 우리는 스택 재귀를 줄이고 최적의 접근 방식을 반복 코드로 변환합니다.

첫 번째 노드는 BST의 루트이므로 루트를 첫 번째 노드로 만들고 스택에 푸시합니다.
선주문 통과 정렬 인덱스 1 (0 기반 인덱싱)에서 각 요소에 대해 현재 요소가 스택의 맨 위보다 크면 맨 위를 튀어 나와 temp라는 변수에 저장합니다.
temp가 null (즉, 현재 요소가 스택의 상단보다 작음)이면 temp를 스택의 상단으로 만들고 현재 요소를 temp의 왼쪽으로 만들고 현재 요소를 스택으로 푸시합니다.
그렇지 않으면 현재 요소를 temp의 오른쪽으로 만들고 현재 요소를 스택으로 푸시합니다.
루트를 반환합니다.

시간 복잡성 = O (N)
공간 복잡성 = O (N)
여기서 n은 사전 주문 배열의 크기입니다.

주어진 선주문 순회에서 생성 BST에 대한 JAVA 코드

import java.util.Stack;

public class ConstructBSTFromGivenPreorderTraversal {
    // 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 inorder 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 createBST(int[] preOrder) {
        // the first element is the root of BST
        Node root = new Node(preOrder[0]);
        // create a stack and push root to it
        Stack<Node> stack = new Stack<>();
        stack.push(root);

        // traverse the array from index 1
        for (int i = 1; i < preOrder.length; i++) {
            // initialize temp as null
            Node temp = null;

            // while current element is greater than top of stack
            // remove top of stack and store it in temp
            while (!stack.isEmpty() && preOrder[i] > stack.peek().data) {
                temp = stack.pop();
            }

            // if temp is null
            if (temp == null) {
                // make temp as top of stack
                temp = stack.peek();
                // current element is left of temp
                temp.left = new Node(preOrder[i]);
                // add current element to stack
                stack.push(temp.left);
            } else {
                // current element is right of temp
                temp.right = new Node(preOrder[i]);
                // add current element to the stack
                stack.push(temp.right);
            }
        }

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int preOrder1[] = new int[] {7, 5, 3, 6, 9};
        Node root1 = createBST(preOrder1);
        inorder(root1);
        System.out.println();

        // Example 2
        int preOrder2[] = new int[] {12, 6, 1, 35, 20};
        Node root2 = createBST(preOrder2);
        inorder(root2);
        System.out.println();
    }
}

3 5 6 7 9 
1 6 12 20 35

지정된 선주문 순회에서 생성 BST를위한 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; 
    } 
};

// 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* createBST(int *preOrder, int n) {
    // the first element is the root of BST
    Node *root = new Node(preOrder[0]);
    // create a stack and push root to it
    stack<Node*> st;
    st.push(root);
    
    // traverse the array from index 1
    for (int i = 1; i < n; i++) {
        // initialize temp as null
        Node *temp = NULL;
        
        // while current element is greater than top of stack
        // remove top of stack and store it in temp
        while (!st.empty() && preOrder[i] > st.top()->data) {
            temp = st.top();
            st.pop();
        }
        
        // if temp is null
        if (temp == NULL) {
            // make temp as top of stack
            temp = st.top();
            // current element is left of temp
            temp->left = new Node(preOrder[i]);
            // add current element to stack
            st.push(temp->left);
        } else {
            // current element is right of temp
            temp->right = new Node(preOrder[i]);
            // add current element to the stack
            st.push(temp->right);
        }
    }
    
    // return root
    return root;
}

int main() {
    // Example 1
    int preOrder1[] = {7, 5, 3, 6, 9};
    Node *root1 = createBST(preOrder1, sizeof(preOrder1) / sizeof(preOrder1[0]));
    inOrder(root1);
    cout<<endl;

    // Example 2
    int preOrder2[] = {12, 6, 1, 35, 20};
    Node *root2 = createBST(preOrder2, sizeof(preOrder2) / sizeof(preOrder2[0]));
    inOrder(root2);
    cout<<endl;
    
    return 0;
}

3 5 6 7 9 
1 6 12 20 35

레퍼런스 1 참조 2

Twitter Facebook 링크드인 버퍼 레딧 텀블러