Remove Duplicates from Sorted List II.png
Convert Sorted List to Balanced BST.png
解題思路 ：
利用 sort 好的 list 持續的二分法把 list 分左右兩半 正中央的數值存入 node 中 然後改動 head 的位置到下一個 ( pass by reference 才能對上一層的 recursive function 作用) 要實際 run 一遍來理解比較容易
C++ code :
<pre><code>
int getSize(ListNode *head)
{
int s = 0;
while(head)
{
s++;
head = head->next;
}
return s;
}
TreeNode* convertTree(ListNode *&head, int size)
{
if(size == 0) return nullptr;
TreeNode *tmp = new TreeNode(0);
tmp->left = convertTree(head, size / 2);
tmp->val = head->val;
head = head->next;
tmp->right = convertTree(head, size - size / 2 - 1);
return tmp;
}
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: a tree node
*/
TreeNode *sortedListToBST(ListNode *head) {
// write your code here
int size = getSize(head);
return convertTree(head, size);
}
};
