109. Convert Sorted List to Binary Search TreeDescriptionHintsSubmissionsSolutionsTotal Accepted: 1

109. Convert Sorted List to Binary Search Tree

与108题类似，给出一个单链表形式的递增序列，求高度平衡的BST，与108题不同的是，108题是递增数组，我们只要遵循：

序列中间值是根，左区间的中间值是根的直接左孩子，右区间的中间值是根的直接右孩子：

数组形式：

TreeNode*buildTree2(vector<int>&postorder,int begin1,int end1,vector<int>& inorder,int begin2,int end2){ if(begin1>end1)return NULL; if(begin1==end1)return (new TreeNode(postorder[end1])); TreeNode *s=new TreeNode(postorder[end1]); int i; for(i=begin2;i<=end2;i++) if(postorder[end1]==inorder[i])break; int k=i-begin2; s->left=buildTree2(postorder,begin1,begin1+k-1,inorder,begin2,begin2+k-1); s->right=buildTree2(postorder,begin1+k,end1-1,inorder,begin2+k+1,end2); return s; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { return buildTree2(postorder,0,postorder.size()-1,inorder,0,inorder.size()-1); }链表形式：

最直接想法也是参考108题，先利用空间消耗转换为数组形式，发现对空间报错：

TreeNode* ToBST(vector<int> nums,int left,int right){ if(left>right)return NULL; int mid=(left+right)/2; TreeNode *root=new TreeNode(nums[mid]); root->left=ToBST(nums,left,mid-1); root->right=ToBST(nums,mid+1,right); return root; } TreeNode* sortedListToBST(ListNode* head){ if(head==NULL)return NULL; int i=0; ListNode*p=head; vector<int> nums; while(p){nums.push_back(p->val);i++;p=p->next;} return ToBST(nums,0,i-1); }应该还存在不使用额外空间但是时间复杂度为O(N)的算法：

采用的自低向上的方法，先构造左子树，并设置一个当前指针指向当前子树位置，在构建左子树的同时不断移动链表的头指针，一直到左叶子节点，再构造根节点，移动指针后递归构造右节点。

代码：

ListNode*curp=NULL; TreeNode* ToBST1(int left,int right){ if(left>right)return NULL; int mid=(left+right)/2; TreeNode *lc=ToBST1(left,mid-1); TreeNode *root=new TreeNode(curp->val); root->left=lc; curp=curp->next; root->right=ToBST1(mid+1,right); return root; } TreeNode* sortedListToBST(ListNode* head){ if(head==NULL)return NULL; int i=0; ListNode*p=head;curp=head; while(p){i++;p=p->next;} return ToBST1(0,i-1); }