來到第三週的第六天，題目是 1008. Construct Binary Search Tree from Preorder Traversal，與前兩週不同的是第六天難度依然維持 Medium，還好沒有提升，這題我就想了快兩個小時拉。挑戰賽也來到了二開頭，不知不覺就持續了 2/3，再接再厲繼續加油 👏 👏 👏
今天的題目是給定一個 Preorder 順序的陣列，要建出 Binary Tree，關於 BT 的介紹可以參考這篇，介紹的很詳細。
Input: [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12]
有了前幾週的洗禮，慢慢地開始有些解題的感覺，希望之後能夠慢慢縮短 Medium 的解題時間，甚至可以朝 High 邁進。
這題的解題思路是透過 Stack 來實作，檢查 top 值是否比目前的小，不是就把前一個記下來然後 pop，直到找到 top 比較大或 stack 為空停止。
接下來就是看如果 current 不為空，表示比記下來的大要擺 right，不然就是擺 left，這樣把 input 陣列全部跑完就完成囉。
TreeNode* bstFromPreorder(vector<int>& preorder) {
if(preorder.empty())
return NULL;
TreeNode* root = new TreeNode(preorder[0]);
TreeNode* current;
stack<TreeNode*> s;
s.push(root);
for(int i=1; i< preorder.size(); i++) {
current = NULL;
while(!s.empty() && preorder[i] > s.top()->val){
current = s.top();
s.pop();
}
if ( current != NULL) {
current->right = new TreeNode(preorder[i]);
s.push(current->right);
} else {
current = s.top();
current->left = new TreeNode(preorder[i]);
s.push(s.top()->left);
}
}
return root;
}