LeetCode OJ：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.

由于对于这个二叉搜索树的要求是其必须是其必须是平衡的，所以应该使用递归。首先找到二叉树的中点。然后由这个中点作为根节点递归的在从左右子树上面取节点构成一颗二叉树。代码如下所示：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 /**
10  * Definition for a binary tree node.
11  * struct TreeNode {
12  *     int val;
13  *     TreeNode *left;
14  *     TreeNode *right;
15  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
16  * };
17  */
18 class Solution {
19 public:
20     int getLen(ListNode * head)
21     {
22         int count = 0;
23         while(head){
24             head = head->next;
25             count++;
26         }
27         return count;
28     }
29 
30     TreeNode * createBST(ListNode * head, int beg, int end)
31     {
32         if(beg > end)
33             return NULL;
34         int mid = beg + (end - beg)/2;
35         ListNode * p = head;
36         for(int i = beg; i < mid; ++i){
37             p = p->next;
38         }
39         TreeNode * leftNode = createBST(head, beg, mid - 1);
40         TreeNode * rightNode = createBST(p->next, mid + 1, end);
41         TreeNode * root = new TreeNode(p->val);
42         root->left = leftNode;
43         root->right = rightNode;
44         return root;
45     }
46     TreeNode* sortedListToBST(ListNode* head) {
47         return createBST(head, 0, getLen(head) - 1);                        
48     }
49 };