متوازن لسٽ BST کي ترتيب ڏني وئي


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon ڪريو
ثنائي ڳولا وارو وڻ بائنري وڻ ڳن -يل فهرست وڻن

متوازن بي ايس ٽي مسئلي جي حل ٿيل ڳن listيل لسٽ ۾ ، اسان هڪ ڳائي ڏني آهي ڳن listيل لسٽ ترتيب وار ترتيب سان ، ھڪڙي ڳن Linkedيل لسٽ مان ھڪڙي متوازن بائنري وڻ ٺاھيو.

مثال

پٽ
1 -> 2 -> 3 -> 4 -> 5
پيداوار

متوازن لسٽ BST کي ترتيب ڏني وئي

پهرين آرڊر: 3 2 1 5 4

پٽ
7 -> 11 -> 13 -> 20 -> 22 -> 41
پيداوار

متوازن لسٽ BST کي ترتيب ڏني وئي

اڳ آرڊر: 20 11 7 13 41 22

نائي اچڻ وارو

جيڪڏهن اسان ويجهڙائي کان ڏسون ، اسان ڏسي سگهون ٿا ته ڳن listيل فهرست جو وچيون پاڙو هميشه بي ايس ٽي جو روٽ هوندو آهي ، ۽ وچ واري نوڊ کان اڳ موجود عنصر کاٻي پاسي جي نن treeي ٽڪر کي ٺاهيندا آهن ۽ وچون نڊ جي وچ ۾ موجود عناصر سا elementsي ذيلي وڻ کي ٺاهيندا آهن.
تنهنڪري مٿئين طريقي سان ٻيهر کاٻي پاسي کان دائیں ۽ کاٻي طرف وار پڻ شامل ڪرڻ سان ، اسان متوازن بائنري تلاش ڪري سگهون ٿا وڻن.

  1. ڳن listيل لسٽ کي ڳوليو ۽ وچين عنصر کي ڳوليو. ان لاءِ ميموري مختص ڪيو ۽ ان کي روٽ بڻائي ڇڏيو.
  2. اعلى کاٻي پاسي تائين وار وٺو ، وچين کي پاڙون ڳوليو ، ۽ ورجائيندا. کاٻي جي اڌ تائين وڃڻ جي روٽ کي کاٻي جي حصي جي حوالي ڪريو.
  3. اعلى طور تي اهو اڌ لاءِ ڇا به ڪريو ، وچين کي ڳوليو ۽ ان کي ٻيڻ ڏيو. سا halfي اڌ جو روٽ حق جي سا toي طرف ڏيو.

وقت جي پيچيدگي = اي (اين لاگ (اين))
خلائي پيچيدگي = اي (ن)، تڪرار جي سبب
جتي ڳن theيل لسٽ ۾ اين نوڊ جو تعداد ڪهڙو آهي.

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

ترتيب وار ڳن Listيل لسٽ کي متوازن 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

ڪوشان وارو رستو

مٿين نقشن کي بھتر بناي سگھجي ٿي جيڪڏھن اسان وڻ کي رھا ڪري سگھن ٿا پتي نوڊس کان وٺي وڻ جي روٽ تائين.
خيال اهو آهي ته کاٻي ـ سبي وڻ کي تعمير ڪيو وڃي ، پوءِ پاڙ ۽ پوءِ سا subي سب-وڻ ۽ انهن کاٻي ۽ سا subي سب-وڻ کي پاڙ سان ڳن attachيو وڃي.

  1. ڏنل ڳن listيل لسٽ ۾ نوڊ جو تعداد ڳڻيو. ان کي ٿيڻ ڏيو.
  2. پوءِ 3 کان 5 تائين ورجائي وٺو.
  3. پهريون n / 2 نوڊس کاٻي نن subي وڻ جو جوڙيو ، تفاوت سان مرحلن 3 کان 5 تائين پهرين n / 2 nodes مان کاٻي ذيلي وڻ جو جوڙڻ لاءِ.
  4. ايندڙ نوڊ بعد n / 2 نوڊس BST جو روٽ ٺاھي ٿو.
  5. باقي ذيلي وڻ کان باقي نوڊس ، وقتي طور تي 3 کان 5 تائين مرحلا وار طور نوڊس مان صحيح ذيلي وڻ ٺاهڻ لاءِ.
  6. کاٻي ۽ سا subي ذيلي وڻ کي پاڙي سان پھچ.

وقت جي پيچيدگي = اي (ن)
خلائي پيچيدگي = اي (ن)، تڪرار جي سبب
جتي ڳن theيل لسٽ ۾ اين نوڊ جو تعداد ڪهڙو آهي.

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

ترتيب وار ڳن Listيل لسٽ کي متوازن 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

حوالا