首页 > 代码库 > [LeetCode 题解]:Convert Sorted List to Binary Search Tree
[LeetCode 题解]:Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
题意：给定一个有序的链表，将其转换成平衡二叉搜索树
思路： 二分法
要构建一个平衡二叉树，二分法无疑是合适的，至于如何分是的代码简洁，就需要用到递归了。
class Solution {public: // find middle element of the list ListNode *getmiddleList(ListNode *left,ListNode *right){ //omit the condition : left!=right && left->next!=right ListNode *pre,*last; pre=left; last =left->next; while(last!=right){ last = last->next; if(last!=right){ last = last->next; pre=pre->next; } } return pre; } // retri-BST constructor TreeNode *getBST(ListNode *left,ListNode *right){ TreeNode *root = new TreeNode(0); //no leaf if(left==right) return NULL; // only one leaf if(left->next == right){ root->val=left->val; return root; } //more than one leaf ListNode *middle =getmiddleList(left,right); root->val = middle->val; root->left = getBST(left, middle); root->right = getBST(middle->next,right); return root; } TreeNode *sortedListToBST(ListNode *head) { TreeNode* root= new TreeNode(0); if(head==NULL) return NULL; if(head->next==NULL){ root->val=head->val; root->left=root->right=NULL; return root; } ListNode *left,*middle,*right; middle=left=head; right=head->next; while(right){ right=right->next; if(right){ right=right->next; middle=middle->next; } } root->val=middle->val; root->left = getBST(left, middle); root->right= getBST(middle->next,right); return root; }};
转载请注明出处： http://www.cnblogs.com/double-win/ 谢谢！
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。