來到第三週的第六天,題目是 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;
    }

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料