균형 BST로 정렬 된 연결 목록

난이도 중급
자주 묻는 질문 아마존 Facebook
이진 검색 트리 이진 트리 연결된 목록 나무조회수 78

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

균형 잡힌 BST 문제에 대한 정렬 된 연결 목록에서 우리는 연결된 목록 정렬 된 순서로 단일 연결 목록에서 균형 이진 트리를 구성합니다.

입력
1-> 2-> 3-> 4-> 5
산출

균형 BST로 정렬 된 연결 목록

선주문 : 3 2 1 5 4

입력
7-> 11-> 13-> 20-> 22-> 41
산출

균형 BST로 정렬 된 연결 목록

선주문 : 20 11 7 13

순진한 접근

자세히 살펴보면 링크드리스트의 중간 노드는 항상 BST의 루트이며, 중간 노드 이전에 존재하는 요소는 왼쪽 하위 트리를 형성하고 중간 노드 이후에 존재하는 요소는 오른쪽 하위 트리를 형성한다는 것을 알 수 있습니다.
따라서 위의 접근 방식을 왼쪽 및 오른쪽 하위 트리에서도 재귀 적으로 반복하여 균형 이진 검색을 구성 할 수 있습니다. 나무.

  1. 연결 목록을 탐색하고 중간 요소를 찾으십시오. 메모리를 할당하고 루트로 만드십시오.
  2. 반복적으로 왼쪽 절반에 대해이 작업을 수행하고 중간을 찾아 루트로 만든 다음 반복합니다. 왼쪽 절반의 루트를 루트의 왼쪽에 할당합니다.
  3. 오른쪽 절반에 대해서도 재귀 적으로 수행하고 중간을 찾아 루트로 만들고 반복하십시오. 오른쪽 절반의 근을 근의 오른쪽에 할당합니다.

시간 복잡성 = O (n 로그 (n))
공간 복잡성 = O (N), 재귀로 인해
여기서 n은 연결된 목록의 노드 수입니다.

정렬 된 연결 목록을 균형 BST로 변환하는 JAVA 코드

public class SortedLinkedListToBalancedBST {
    // class representing node of a linked list
    static class ListNode {
        int data;
        ListNode next;

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

    // class representing node of a tree
    static class TreeNode {
        int data;
        TreeNode left, right;

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

    // function to print the pre order traversal of a tree
    private static void preOrder(TreeNode root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    private static TreeNode convertToBalancedBST(ListNode node) {
        // if the node is null, return null
        if (node == null) {
            return null;
        }

        // Count the number of nodes in the linked list
        ListNode temp = node;
        int n = 0;
        while (temp != null) {
            temp = temp.next;
            n++;
        }

        if (n == 1) {
            return new TreeNode(node.data);
        }

        // First n/2 nodes contributes to the left subtree
        ListNode leftHalf = new ListNode(node.data);
        ListNode leftTemp = leftHalf;
        for (int i = 0; i < n/2 - 1; i++) {
            node = node.next;
            leftTemp.next = new ListNode(node.data);
            leftTemp = leftTemp.next;
        }

        node = node.next;
        // node is pointing to the middle element of the list
        // make this element as the root of the BST
        TreeNode root = new TreeNode(node.data);

        // move node ahead
        node = node.next;

        // Remaining nodes form the right subtree of the BST
        ListNode rightHalf = null;
        if (node != null) {
             rightHalf = new ListNode(node.data);
            ListNode rightTemp = rightHalf;
            node = node.next;
            while (node != null) {
                rightTemp.next = new ListNode(node.data);
                rightTemp = rightTemp.next;
                node = node.next;
            }
        }

        // Recursively call the method for left and right halfs
        root.left = convertToBalancedBST(leftHalf);
        root.right = convertToBalancedBST(rightHalf);

        return root;
    }

    public static void main(String[] args) {
        // Example 1
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(2);
        node1.next.next = new ListNode(3);
        node1.next.next.next = new ListNode(4);
        node1.next.next.next.next = new ListNode(5);

        TreeNode root1 = convertToBalancedBST(node1);
        preOrder(root1);
        System.out.println();

        // Example 2
        ListNode node2 = new ListNode(7);
        node2.next = new ListNode(11);
        node2.next.next = new ListNode(13);
        node2.next.next.next = new ListNode(20);
        node2.next.next.next.next = new ListNode(22);
        node2.next.next.next.next.next = new ListNode(41);

        TreeNode root2 = convertToBalancedBST(node2);
        preOrder(root2);
        System.out.println();
    }
}
3 2 1 5 4 
20 11 7 13 41 22

정렬 된 연결 목록을 균형 BST로 변환하는 C ++ 코드

#include <iostream>
using namespace std;

// class representing node of a linked list
class ListNode {
    public:
    int data;
    ListNode *next;
    
    ListNode(int d) {
        data = d;
    }
};

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

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

TreeNode* convertToBalancedBST(ListNode *node) {
    // if the node is null, return null
    if (node == NULL) {
        return NULL;
    }
    
    // Count the number of nodes in the linked list
    ListNode *temp = node;
    int n = 0;
    while (temp != NULL) {
        n++;
        temp = temp->next;
    }
    
    if (n == 1) {
        return new TreeNode(node->data);
    }
    
    // First n/2 nodes contributes to the left subtree
    ListNode *leftHalf = new ListNode(node->data);
    ListNode *leftTemp = leftHalf;
    for (int i = 0; i < n/2 - 1; i++) {
        node = node->next;
        leftTemp->next = new ListNode(node->data);
        leftTemp = leftTemp->next;
    }
    
    node = node->next;
    // node is pointing to the middle element of the list
    // make this element as the root of the BST
    TreeNode *root = new TreeNode(node->data);
    
    // move node ahead
    node = node->next;
    
    // Remaining nodes form the right subtree of the BST
    ListNode *rightHalf = NULL;
    if (node != NULL) {
        rightHalf = new ListNode(node->data);
        ListNode *rightTemp = rightHalf;
        node = node->next;
        while (node != NULL) {
            rightTemp->next = new ListNode(node->data);
            rightTemp = rightTemp->next;
            node = node->next;
        }
    }
    
    // Recursively call the method for left and right halfs
    root->left = convertToBalancedBST(leftHalf);
    root->right = convertToBalancedBST(rightHalf);
    
    return root;
}

int main() {
    // Example 1
    ListNode *node1 = new ListNode(1);
    node1->next = new ListNode(2);
    node1->next->next = new ListNode(3);
    node1->next->next->next = new ListNode(4);
    node1->next->next->next->next = new ListNode(5);

    TreeNode *root1 = convertToBalancedBST(node1);
    preOrder(root1);
    cout<<endl;

    // Example 2
    ListNode *node2 = new ListNode(7);
    node2->next = new ListNode(11);
    node2->next->next = new ListNode(13);
    node2->next->next->next = new ListNode(20);
    node2->next->next->next->next = new ListNode(22);
    node2->next->next->next->next->next = new ListNode(41);

    TreeNode *root2 = convertToBalancedBST(node2);
    preOrder(root2);
    cout<<endl;
    
    return 0;
}
3 2 1 5 4 
20 11 7 13 41 22

최적의 접근 방식

위의 접근 방식은 리프 노드에서 트리의 루트까지 트리를 구축하면 최적화 될 수 있습니다.
아이디어는 왼쪽 하위 트리를 만든 다음 루트 및 오른쪽 하위 트리를 만들고 왼쪽 및 오른쪽 하위 트리를 루트에 연결하는 것입니다.

  1. 주어진 연결 목록의 노드 수를 세십시오. n이라고합시다.
  2. 그런 다음 3 ~ 5 단계를 반복합니다.
  3. 첫 번째 n / 2 노드는 왼쪽 하위 트리를 형성하고, 3 ~ 5 단계를 반복적으로 호출하여 첫 ​​번째 n / 2 노드에서 왼쪽 하위 트리를 형성합니다.
  4. n / 2 노드 다음의 다음 노드는 BST의 루트를 형성합니다.
  5. 오른쪽 하위 트리의 나머지 노드는 3 ~ 5 단계를 재귀 적으로 호출하여 나머지 노드에서 오른쪽 하위 트리를 형성합니다.
  6. 루트가있는 왼쪽 및 오른쪽 하위 트리를 연결합니다.

시간 복잡성 = O (N)
공간 복잡성 = O (N), 재귀로 인해
여기서 n은 연결된 목록의 노드 수입니다.

정렬 된 연결 목록을 균형 BST로 변환하는 JAVA 코드

public class SortedLinkedListToBalancedBST {
    // class representing node of a linked list
    static class ListNode {
        int data;
        ListNode next;

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

    // class representing node of a tree
    static class TreeNode {
        int data;
        TreeNode left, right;

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

    private static ListNode globalNode = null;

    // function to print the pre order traversal of a tree
    private static void preOrder(TreeNode root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    private static TreeNode convertToBalancedBST(ListNode node) {
        // Count the number of nodes in the list
        int n = 0;
        ListNode temp = node;
        while (temp != null) {
            n++;
            temp = temp.next;
        }

        // this to use the node by reference
        globalNode = node;
        return convertToBalancedBSTRecursive(n);
    }

    private static TreeNode convertToBalancedBSTRecursive(int n) {
        if (n <= 0) {
            return null;
        }

        // recursively construct the left subtree
        // left subtree contains n/2 nodes
        TreeNode leftSubTree = convertToBalancedBSTRecursive(n/2);

        // construct the root node
        TreeNode root = new TreeNode(globalNode.data);
        // move one step ahead
        globalNode = globalNode.next;

        // link the left subtree with root
        root.left = leftSubTree;

        // construct right subtree and link it with root
        // right subtree contains (n - n/2 - 1) nodes
        root.right = convertToBalancedBSTRecursive(n - n/2 - 1);

        // return the root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(2);
        node1.next.next = new ListNode(3);
        node1.next.next.next = new ListNode(4);
        node1.next.next.next.next = new ListNode(5);

        TreeNode root1 = convertToBalancedBST(node1);
        preOrder(root1);
        System.out.println();

        // Example 2
        ListNode node2 = new ListNode(7);
        node2.next = new ListNode(11);
        node2.next.next = new ListNode(13);
        node2.next.next.next = new ListNode(20);
        node2.next.next.next.next = new ListNode(22);
        node2.next.next.next.next.next = new ListNode(41);

        TreeNode root2 = convertToBalancedBST(node2);
        preOrder(root2);
        System.out.println();
    }
}
3 2 1 5 4 
20 11 7 13 41 22

정렬 된 연결 목록을 균형 BST로 변환하는 C ++ 코드

#include <iostream>
using namespace std;

// class representing node of a linked list
class ListNode {
    public:
    int data;
    ListNode *next;
    
    ListNode(int d) {
        data = d;
    }
};

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

ListNode *globalNode = NULL;

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

TreeNode* convertToBalancedBSTRecursive(int n) {
    if (n <= 0) {
        return NULL;
    }
    
    // recursively construct the left subtree
    // left subtree contains n/2 nodes
    TreeNode *leftSubTree = convertToBalancedBSTRecursive(n/2);
    
    // construct the root node
    TreeNode *root = new TreeNode(globalNode->data);
    // move one step ahead
    globalNode = globalNode->next;
    
    // link the left subtree with root
    root->left = leftSubTree;
    
    // construct right subtree and link it with root
    // right subtree contains (n - n/2 - 1) nodes
    root->right = convertToBalancedBSTRecursive(n - n/2 - 1);
    
    // return the root
    return root;
}

TreeNode* convertToBalancedBST(ListNode *node) {
    // Count the number of nodes in the list
    int n = 0;
    ListNode *temp = node;
    while (temp != NULL) {
        n++;
        temp = temp->next;
    }
    
    globalNode = node;
    return convertToBalancedBSTRecursive(n);
}

int main() {
    // Example 1
    ListNode *node1 = new ListNode(1);
    node1->next = new ListNode(2);
    node1->next->next = new ListNode(3);
    node1->next->next->next = new ListNode(4);
    node1->next->next->next->next = new ListNode(5);

    TreeNode *root1 = convertToBalancedBST(node1);
    preOrder(root1);
    cout<<endl;

    // Example 2
    ListNode *node2 = new ListNode(7);
    node2->next = new ListNode(11);
    node2->next->next = new ListNode(13);
    node2->next->next->next = new ListNode(20);
    node2->next->next->next->next = new ListNode(22);
    node2->next->next->next->next->next = new ListNode(41);

    TreeNode *root2 = convertToBalancedBST(node2);
    preOrder(root2);
    cout<<endl;
    
    return 0;
}
3 2 1 5 4 
20 11 7 13 41 22

참조

균열 시스템 설계 인터뷰
Translate »