1、

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.

分析：将一个升序排列的链表转换为平衡二叉搜索树，採用递归的方式，先找到链表的中点，作为二叉树的根，然后递归求解左右子树。

例如以下：

class Solution {

public:

    TreeNode *sortedListToBST(ListNode *head) {

        if(!head){

            return NULL;

        }

        if(!head->next){

            return new TreeNode(head->val);

        }

        ListNode* midNode = findMidNode(head);

        TreeNode* root = new TreeNode(midNode->val);

        TreeNode* leftSubTree = sortedListToBST(head);

        TreeNode* rightSubTree = sortedListToBST(midNode->next);

        if(leftSubTree){

            root->left = leftSubTree;

        }

        if(rightSubTree){

            root->right = rightSubTree;

        }

        return root;

    }

    ListNode* findMidNode(ListNode* head){

        ListNode* node1 = head;

        if(!node1->next){

            return node1;

        }

        ListNode* node2 = head->next;

        while(node2 && node2->next && node2->next->next){

            node2 = node2->next;

            node2 = node2->next;

            node1 = node1->next;

        }

        ListNode* midNode = node1->next;

        node1->next = NULL;

        return midNode;

    }

};