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

 

Hide Tags

   

 

---

    这题是将链表变成二叉树，比较麻烦的遍历过程，因为链表的限制，所以深度搜索的顺序恰巧是链表的顺序，通过设置好递归函数的参数，可以在深度搜索时候便可以遍历了。

 

TreeNode * help_f(ListNode *&curList,int lft,int rgt)

 

全部代码：

#include 
      
       using namespace std;/** * Definition for singly-linked list. */struct ListNode {    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};/** * Definitiosn for binary tree */struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:    TreeNode *sortedListToBST(ListNode *head) {        int len=0;        ListNode * p = head;        while(p!=NULL){            len++;            p=p->next;        }//        cout<
       
        <
        
         rgt) return  NULL;        int mid=(lft+rgt)/2;        TreeNode *lftCld = help_f(curList,lft,mid-1);        TreeNode *parent =new TreeNode(curList->val);        parent->left=lftCld;        curList=curList->next;        parent->right=help_f(curList,mid+1,rgt);        return parent;    }};int main(){    ListNode n1(0);    Solution sol;    sol.sortedListToBST(&n1);    return 0;}