1.Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

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

这里两道题目。是连在一起的两题。给你一个排好序（升序）的数组或者链表，将它们转为一棵平衡二叉树。如果不排好序的话。一组随机输入的数据，就必须採用RBT或者AVL树，这样操作会变得更复杂。涉及到旋转，可是这里排好序了。所以，仅仅要找到中位数。作为根，然后递归地依据中位数的左、右数列来构建左右子树；

两题的思路都是如上所述， 唯一的差别就是，链表寻找中位数会麻烦一些。须要引入fast、slow两个指针，来寻找中位数。代码例如以下：

1.Array

class Solution {public:    TreeNode *Tree(int left, int right, vector
     
       &num){        TreeNode *root = NULL;        if (left <= right){            int cen = (left + right) / 2;            root = new TreeNode(num[cen]);            root->left = Tree(left, cen - 1, num);            root->right = Tree(cen + 1, right, num);        }        return root;    }        TreeNode *sortedArrayToBST(vector
      
        &num) {        TreeNode *T = NULL;        int N = num.size();        T = Tree(0, N - 1, num);        return T;    }};
      
     

2.link-list

class Solution {public:    ListNode *findMid(ListNode *head){        //这里假设链表中仅仅有两个数字。则mid返回的是head->next.        if (head == NULL || head -> next == NULL)            return head;        ListNode *fast, *slow, *pre;        fast = slow = head;        pre = NULL;        while (fast && fast->next){            pre = slow;            slow = slow->next;            fast = fast->next->next;        }        pre->next = NULL;        return slow;    }        TreeNode *buildTree(ListNode *head){        TreeNode *root = NULL;        ListNode *mid = NULL;        if (head){            mid = findMid(head);            root = new TreeNode(mid->val);            if (head != mid){                root->left = buildTree(head);                root->right = buildTree(mid->next);            }        }        return root;            }        TreeNode *sortedListToBST(ListNode *head) {        TreeNode *T;        T = buildTree(head);        return T;    }};