排序鍊錶到平衡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 log(n))
空間複雜度= O(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

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. 將左和右子樹附加到根。

時間複雜度= O(N)
空間複雜度= O(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;
        }
    }

    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

參考