题目：将非递减有序的链表转化为平衡二叉查找树！

参考的博客：

利用递归思想：首先找到链表的中间节点，于是链表被分为了由该中间节点划分开来的两部分。递归地处理这两部分，最终便得到了平衡二叉查找树。

 

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     TreeNode* sortedListToBST(ListNode* head) {21         if(!head)22             return NULL;23         if(head->next==NULL){24             TreeNode*root=new TreeNode(head->val);25             return root;26         }27         ListNode*pre=getLeftOfMid(head),*mid=pre->next;28         TreeNode*root=new TreeNode(mid->val);//根29         pre->next=NULL;30         root->left=sortedListToBST(head);//左子树31         root->right=sortedListToBST(mid->next);//右子树32         return root;33     }34     ListNode* getLeftOfMid(ListNode*head)//说简单点，就是获取链表中间节点，作为树的根节点，并由此划分根的2个子树35     {36         if(!head)37             return NULL;38         ListNode*pre=head,*back=head;39         while(back!=NULL)//back后退的步数大致是head的两倍，确保pre能落在中间节点位置的前一结点处40         {41             back=back->next;42             if(!back)43                 break;44             back=back->next;45             if(!back)46                break;47             pre=head;48             head=head->next;49         }50         return pre;51     }52 };

 上面的方法是一种自顶向下的方法，先找到root然后对左右子树分别递归调用。

网上又看到一种自底向上的方法，算法复杂度为O(N)。先递归构建左子树，在构建左子树的同时不断移动链表的头指针，链表的头指针永远是对应当前子树位置的。一直到左叶子节点，左叶子节点对应的就是链表的第一个元素，生成左叶子节点之后移动链表当前指针。

看这个博客

这里的问题是对于一个链表我们是不能常量时间访问它的中间元素的。这时候就要利用到树的中序遍历了，按照递归中序遍历的顺序对链表结点一个个进行访问，而我们要构造的二分查找树正是按照链表的顺序来的。思路就是先对左子树进行递归，然后将当前结点作为根，迭代到下一个链表结点，最后在递归求出右子树即可。整体过程就是一次中序遍历，时间复杂度是O(n)，空间复杂度是栈空间O(logn)。

来看一下对应数组的中序遍历建立BST代码：

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 private:12      int cur;//不去掉这前面的static编译不会通过的13 public:14     TreeNode* sortedArrayToBST(vector
     
      & nums) {15         cur = 0;16         if (nums.size() == 0)17             return NULL;18         return helper(nums, 0, nums.size() - 1);19     }20     TreeNode* helper(vector
      
       &nums, int l, int r)21     {22         if (l > r)23             return NULL;24         int mid = (l+r) / 2;25         TreeNode*left=helper(nums, l, mid-1);26         TreeNode * root = new TreeNode(nums[cur++]);//回忆考研时候，中序遍历中，这个地方才是真正干活的语句（并且终须遍历二叉排序树得到的就是有序数组）27         root->left = left;28         root->right = helper(nums, mid + 1, r);29         return root;30     }31 };