單向鏈表轉平衡二叉搜索樹 - acm1314－IT工程師數位筆記本

文章出處

題目描述

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

給一個排了序的單向鏈表，把它轉換成平衡二叉搜索樹。

我的笨代碼

/**
 * 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) {
        if(head == NULL)
            return NULL; 
        
        vector<int> temp; 
        while(head != NULL)
        {
            temp.push_back(head->val); 
            head = head->next; 
        }
        
        return vecToBST(temp); 
        
    }
    
private: 
    TreeNode* vecToBST(vector<int> &node)
    {
        if(node.size() == 0)
            return NULL; 
        
        int len = node.size(); 
        TreeNode *root = new TreeNode(node[ len/2 ]); 
        vector<int> left(node.begin(), node.begin() + len/2); 
        vector<int> right(node.begin() + len/2 + 1, node.end()); 
        root->left = vecToBST(left); 
        root->right = vecToBST(right); 
        
        return root;
    }
};

參考別人的代碼

（平衡）二叉樹搜索樹的中序變量可以是一個排了序的單向鏈表，可以用左右子樹的節點個數，控制二叉搜索樹是一個平衡二叉搜索樹。

/**
 * 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 {
private:
    ListNode* list; 
    
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(head == NULL)
            return NULL; 
        
        list = head; 
        return generate(count(head)); 
    }
    
private:
    // 計數
    int count(ListNode* pos)
    {
        int size = 0; 
        while(pos != NULL)
        {
            size++; 
            pos = pos->next; 
        }
        
        return size; 
    }
    
    // 按照計數和中序遍歷構造平衡二叉搜索樹
    TreeNode* generate(int n)
    {
        if(n == 0)
            return NULL; 
        
        TreeNode* node = new TreeNode(0); 
        node->left = generate(n/2); 
        node->val = list->val; 
        list = list->next; 
        node->right = generate(n - n/2 - 1); 
        
        return node; 
    }
};