首页 > 代码库 > 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.
分析：我们比较熟悉由一个sorted array生成一个BST，不同的是这里的数据结构换为了linked list。我们同样可以用递归的方法生成BST，与数组不同的是我们需要先确定linked list的中间结点。
class Solution {public: TreeNode *sortedListToBST(ListNode *head) { if(head == NULL) return NULL; if(head->next == NULL){ TreeNode *root = new TreeNode(head->val); return root; } //get length int n = 0; for(ListNode *p = head; p; p = p->next) n++; //find middle point ListNode *prev = NULL, *mid = head; for(int i = 0; i < (n-1)/2; i++){ prev = mid; mid = mid->next; } TreeNode *root = new TreeNode(mid->val); if(prev) prev->next = NULL; if(mid != head) root->left = sortedListToBST(head); root->right = sortedListToBST(mid->next); return root; }};
Leetcode: Convert Sorted List to Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。