题目描述

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