Отсортированный связанный список в сбалансированный BST


Сложный уровень средний
Часто спрашивают в Амазонка 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 - количество узлов в связанном списке.

Код 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

Код C ++ для преобразования отсортированного связного списка в сбалансированный 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. Подсчитайте количество узлов в данном связанном списке. Пусть это будет n.
  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

Код C ++ для преобразования отсортированного связного списка в сбалансированный 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

дело