Leetcode -- Convert Sorted List to Binary Search Tree

題目：

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

分析：

将排好序的連結清單，轉為平衡二叉搜尋樹。

思路：

連結清單的中間那個node是樹的根節點，前面是左子樹，後面是右子樹。以此，不斷遞歸就可以得到平衡二叉樹。時間複雜度是O（NlogN）；

代碼：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        TreeNode* root = new TreeNode();
        if(!head) return NULL;
        if(head && !head->next)
        {
            root->val = head->val;
            return root;
        }
        else
        {
            ListNode* slow;
            ListNode* fast;

            int len = ;
            slow = head;
            while(slow)
            {
                len++;
                slow = slow->next;
            }
            slow = head;
            fast = head;
            len = len/;
            while(len)
            {
                fast = slow;
                slow = slow->next;
                len --;
            }
            root->val = slow->val;
            slow = slow->next;
            fast->next = NULL;
            fast = head;
            root->left = sortedListToBST(fast);
            root->right = sortedListToBST(slow);
            return root;
        }
    }
};
           

簡潔的代碼【引自：https://leetcode.com/discuss/29826/clean-c-solution-recursion-o-nlogn-with-comment】：

class Solution {
    public:
        TreeNode *sortedListToBST(ListNode *head) {
            if(!head) return NULL;
            if(!head->next) return new TreeNode(head->val);

        // fast/slow pointer to find the midpoint
        auto slow = head;
        auto fast = head;
        auto pre = head;
        while(fast && fast->next) {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = ; // break two halves 

        // slow is the midpoint, use as root
        TreeNode* root = new TreeNode(slow->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(slow->next);

        return root;
    }
};

           

複雜度是O(n)【引自：https://leetcode.com/discuss/10924/share-my-code-with-o-n-time-and-o-1-space】：

class Solution {
public:
    ListNode *list;
    int count(ListNode *node){
        int size = ;
        while (node) {
            ++size;
            node = node->next;
        }
        return size;
    }

    TreeNode *generate(int n){
        if (n == )
            return NULL;
        TreeNode *node = new TreeNode();
        node->left = generate(n / );
        node->val = list->val;
        list = list->next;
        node->right = generate(n - n /  - );
        return node;
    }

    TreeNode *sortedListToBST(ListNode *head) {
        this->list = head;
        return generate(count(head));
    }
};