Convert Sorted List to Binary Search Tree

自底向上的解释

http://bangbingsyb.blogspot.com/2014/11/leetcode-convert-sorted-list-to-binary.html

class Solution {

public:

TreeNode sortedListToBST(ListNode head) {

ListNode *p= head;

int n=0;

while(p){

n++;

p=p->next;

}

return helper(head,0,n-1);

}

TreeNode helper(ListNode& head, int s, int e){//指针的引用

if(s>e)

return nullptr;

int mid=s+(e-s)/2;

TreeNode *l = helper(head,s,mid-1);

TreeNode *r=new TreeNode(head->val);

r->left=l;

head=head->next;

r->right = helper(head,mid+1,e);

return r;

}