Convert Sorted List to Balanced BST
Description:
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Example:
2
1->2->3 => /
1 3
分析:
最简单的办法是把链表变成一个vector
,然后按照这个题目来就行了。
另一个方法是按照bottom-up
的方式,把孩子节点挂到父亲节点上,这就需要递归实现,每次退出当前递归就把当前节点返回给父节点。代码如下。
参考:
Convert Sorted List to Balanced Binary Search Tree (BST)
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
|
class Solution { public:
TreeNode *sortedListToBST(ListNode *head) { if (head == nullptr) return nullptr; ListNode *curr = head; int n = 0; while(curr != nullptr) { n++; curr = curr->next; } return sortedListToBST(head, 0, n-1); } TreeNode* sortedListToBST(ListNode *& list, int start, int end) { if (start > end) return NULL; int mid = start + (end - start) / 2; TreeNode *leftChild = sortedListToBST(list, start, mid-1); TreeNode *parent = new TreeNode(list->val); parent->left = leftChild; list = list->next; parent->right = sortedListToBST(list, mid+1, end); return parent; } };
|