這題會給你一個Linked List，然後要建出一個BST
之前有一題是用陣列的，有興趣可以往前翻翻看
http://yayaya6d.pixnet.net/blog/post/349998112-leetcode%E7%B4%80%E9%8C%84--108.%20Convert%20Sorted%20Array%20to%20Binary%20Search%20Tree
用Linked List顯然看起來困難一些，畢竟你只能從第一個值去往後找
不像陣列就可以直接從中間取值，之前陣列那題的解法就是從中間取值去做的
當然這題也先把List裡的值抓出來做成陣列，然後再開始做
不過那應該就不是這題的本意了
那麼... 排列... BST... 我們就會想到inorder traversal
對於BST，inorder traversal就會列出排好序的數列
所以從這個角度來試試看
說道inorder嘛，我們先複習一下：
void inorder(TreeNode* root)
{
if (root == nullptr) return;
inorder(root->left);
cout << root->val;
inorder(root->right);
}
所以說講道理，大概會變成這種模式：
TreeNode* inorder (ListNode* cur)
{
if (cur == nullptr) return nullptr;
TreeNode* left = inorder(cur);
TreeNode* root = new TreeNode(cur->val);
root->left = left;
root->right = inorder(cur);
return root;
}
當然不可能直接這麼做，因為是要建出Balance的tree，也就是兩邊高度要相同
直接這樣的話就會變成一長串長條狀的tree了
所以我們必須要加一些條件來達到分段的結果
其實可以直接把用陣列做的觀點帶過來用就行了，可以設start和end的值
這個start和end就只是一個達成分段效果的條件而已，這也是我在做這題時的一個盲點...
我一直想不到要怎樣達到這個效果，看了其他網友的作法後才猛然醒悟
首先先找到長度，就可以丟進去解了：
class Solution {
public:
ListNode* cur;
TreeNode* inorder(int start, int end)
{
if (cur == nullptr || start > end)
return nullptr;
int mid = (start + end)/2; // 中間值，其實用陣列的觀點來看，等等root的值就是mid這個index的值
TreeNode* left = inorder(start, mid-1);
TreeNode* root = new TreeNode(cur->val);
cur = cur->next;
root->left = left;
root->right = inorder(mid+1, end);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
cur = head;
int len = 0;
while (head != nullptr)
{
head = head->next;
++len;
}
return inorder(0, len-1);
}
};
看起來有點難吧，我覺得有點難啦...
不過只要把他想成陣列就行了，這也是這題有趣的地方
利用排好序的特性，剛好這樣做就會得到正確的結果
好啦那這題就這樣了~ 繼續努力~
留言列表
