Відсортований пов’язаний список із збалансованим BST


Рівень складності Medium
Часто запитують у Амазонка Facebook
Бінарне дерево пошуку Бінарне дерево Зв’язаний список Дерево

У відсортованому зв’язаному списку із збалансованою проблемою BST ми наводимо окремо Пов'язаний список у відсортованому порядку побудуйте збалансоване двійкове дерево з єдинозв’язаного списку.

прикладів

вхід
1 -> 2 -> 3 -> 4 -> 5
Вихід

Відсортований пов’язаний список із збалансованим BST

Попереднє замовлення: 3 2 1 5 4

вхід
7 -> 11 -> 13 -> 20 -> 22 -> 41
Вихід

Відсортований пов’язаний список із збалансованим BST

Попереднє замовлення: 20 11 7 13 41 22

Наївний підхід

Якщо ми уважно розглянемо, ми побачимо, що середній вузол пов'язаного списку завжди є коренем BST, а елементи, присутні перед середнім вузлом, утворюють ліве піддерево, а елементи, присутні після середнього вузла, формують праве піддерево.
Отже, повторюючи вищезазначений підхід рекурсивно в лівому та правому піддереві, ми також можемо сформувати збалансований двійковий пошук Дерево.

  1. Перейдіть по зв’язаному списку та знайдіть середній елемент. Виділіть для нього пам’ять і зробіть це коренем.
  2. Рекурсивно зробіть це для лівої половини, знайдіть середню, пустіть її корінням, і повторіть. Призначте корінь лівої половини лівій корені.
  3. Рекурсивно робіть це і для правої половини, знайдіть середину, пустіть її корінням і повторіть. Призначте корінь правої половини праворуч кореня.

Складність часу = O (n журнал (n))
Складність простору = О (п), через рекурсію
де n - кількість вузлів у зв'язаному списку.

Код JAVA для перетворення відсортованого пов'язаного списку в збалансований BST

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

#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. Підрахуйте кількість вузлів у даному зв’язаному списку. Нехай це буде н.
  2. Потім повторіть кроки 3 - 5.
  3. Перші n / 2 вузли утворюють ліве піддерево, рекурсивно викликають кроки 3 - 5 для формування лівого піддерева з перших n / 2 вузлів.
  4. Наступний вузол після n / 2 вузлів утворює корінь BST.
  5. Решта вузлів з правого піддерева рекурсивно викликають кроки 3 - 5, щоб сформувати правильне піддерево з решти вузлів.
  6. Приєднайте ліве та праве піддерево з коренем.

Складність часу = О (п)
Складність простору = О (п), через рекурсію
де n - кількість вузлів у зв'язаному списку.

Код JAVA для перетворення відсортованого пов'язаного списку в збалансований BST

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

#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

посилання