LeetCode-109. Convert Sorted List to Binary Search Tree

LeetCode-109. 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.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5

题解：

显然遍历list然后放到vector里用108方法最快，但是我觉得本题意义并非如此。

比较直观的解：

class Solution {public: TreeNode* buildTree(ListNode * &head, int b, int e) { if (b > e) { return NULL; } int mid = (b + e) / 2; ListNode *p = head; for (int i = 0; i < mid; i++) { p = p->next; } TreeNode *root = new TreeNode(p->val); root->left = buildTree(head, b, mid - 1); root->right = buildTree(head, mid + 1, e); return root; } TreeNode* sortedListToBST(ListNode* head) { ListNode *p = head; int n = 0; while (p != NULL) { p = p->next; n++; } TreeNode *root = buildTree(head, 0, n - 1); return root; }};

另一个解法，使用快慢指针获取中点

class Solution {public: TreeNode* sortedListToBST(ListNode* head) { if (head == NULL) { return NULL; } if (head->next == NULL) { return new TreeNode(head->val); } ListNode *p = head, *q = head, *pre = head; while (q != NULL && q->next != NULL) { pre = p; p = p->next; q = q->next->next; } TreeNode *root = new TreeNode(p->val); pre->next = NULL; root->left = sortedListToBST(head); root->right = sortedListToBST(p->next); return root; } };

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。