首页 > 代码库 > Convert Sorted List to Binary Search Tree
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.
思路：使用两个指针分别以1、2的速度遍历链表，以定位出链表的中点，进而将链表分割成三部分：{ 前一段，中点，后一段 }，分别对应所求平衡二叉搜索树的左子树、根节点以及右子树。于是，我们将问题分解为对前一段和后一段两个子链表的求解。使用递归可以很方便地实现。
1 class Solution { 2 public: 3 TreeNode *sortedListToBST( ListNode *head ) { 4 if( !head ) { return 0; } 5 return ConvertSubList( head ); 6 } 7 private: 8 TreeNode* ConvertSubList( ListNode *node ) { 9 if( !node ) { return 0; }10 if( !node->next ) { return new TreeNode( node->val ); }11 ListNode *slow = node, *fast = node->next;12 while( fast->next ) {13 fast = fast->next;14 if( fast->next ) { slow = slow->next; fast = fast->next; }15 }16 TreeNode *treeNode = new TreeNode( slow->next->val );17 fast = slow->next->next;18 slow->next = 0;19 treeNode->left = ConvertSubList( node );20 treeNode->right = ConvertSubList( fast );21 return treeNode;22 }23 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。