给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
算法：可以看出，升序排列的链表即为BST中序遍历的结果。故我们先找到中间结点作为根结点，再递归创建左子树与右子树。
我们可以证明，该算法得到的BST满足：任意节点的左右子树的所有高度的差不大于1（注意不是最大高度）。
在每一次递归过程中，左半部分的长度最多比右半部分的长度少1，那会不会有这种情况：左半部分的高度分别有 m−1,m ，右半部分的高度有 m,m+1，则当前节点的高度就是 m,m+1,m+2（要加上当前根节点这一层，所以都要加1），则此时树的高度差为2，不平衡。
实际上这种情况是不可能的：反证，对于左子树，由于存在高度 m−1,所以左半部分最多有 2^m−2个数；对于右子树，由于存在高度 m和 m+1，所以右半部分最少有 2^m 个数，此时左右两部分的数的个数最少差2，矛盾。
/** * 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)return NULL; int n=0; for(auto p=head;p;p=p->next)n++; n/=2;//为找中间结点做准备 auto p=head; for(int i=0;i<n;i++)p=p->next;//找到中间结点 TreeNode* root=new TreeNode(p->val);//中间结点作为根结点 root->right=sortedListToBST(p->next);//中间结点的右边为右子树 if(n){//只有一个结点时n为0，此时没有必要建左子树 p=head; for(int i=0;i<n-1;i++)p=p->next;//找中间结点的前一个结点 p->next=NULL;//断开 root->left=sortedListToBST(head); } return root; } };
。
原文：https://www.cnblogs.com/programyang/p/11161198.html