[LeetCode][Medium] 199. Binary Tree Right Side View

- 
Leetcode 網址: https://leetcode.com/problems/binary-tree-right-side-view/

題目說明:

給定一個 Binary Tree，請由 Top 至 Bottom 出每一層中最右邊 Node 的值。

解題說明:

題目很清楚，就是一題 Level Order Traversal 的題目，所以直接用 queue 處理即可。

程式碼


class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> q;
        
        if (root) q.push(root);
        while (q.size() > 0) {
            TreeNode* rightNode = NULL;
            for (int i = 0, size = q.size(); i < size; i++, q.pop()) {
                rightNode = q.front();
                if (rightNode->left) q.push(rightNode->left);
                if (rightNode->right) q.push(rightNode->right);
            }
            if (rightNode) ans.push_back(rightNode->val);
        }
        return ans;
    }
};

結果

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Binary Tree Right Side View.
Memory Usage: 11.8 MB, less than 29.31% of C++ online submissions for Binary Tree Right Side View.








留言

張貼留言

這個網誌中的熱門文章

[面試心得] Synology / 群暉 - Product Developr

-
一面. Skype  第一關 1hr. 後端考官 A  先自我介紹, 接著主考官會針對你履歷中的經歷做詢問  (印象中有: 怎麼找 race condition, cookie / session, 解釋 Polymorphism ... 等) 最後就是 Synology 必考的程式題, 題目是矩陣向右旋轉 90 度 (要求 in-place) 由於 leetcode 寫過這題, 很快就寫出 transpose 再 reflect 的解法 因為時間剩蠻多的考官 A 就問有沒有其他寫法, 於是就提出 Rotate Groups of Four Cells 這解法, 但寫的過程不是很順, 因為卡在推 index QQ, 但最後考官 A 叫我不要管 index 寫概念就好, 最後考官會讓你發問你想問的問題 (如: 公司 / 部門 ... 等) 第二關 1hr. 後端考官 B 一樣先自我介紹, 接著主考官會針對你履歷中的經歷做詢問  (印象中有: Load Balancer 可能會遇到什麼問題, 很大的資料庫下有什麼辦法加速查詢, struct 跟 class 的差異 ... 等) 最後也是 Synology 必考的程式題, 題目是實作 linked list 的 class 實作過程中考官 B 會慢慢要你增加一些功能, 並詢問你的寫法 (印象中有: nullptr 跟 NULL 差異, const int * 跟 int * const ... 等) 一樣最後考官會讓你發問你想問的問題 二面. 現場 第一關 1hr. HR 基本上就是在認識你的背景, 如: 前份工作為何離職, 怎麼會想來 Synology, 未來想走的方向 ... 等 第一關 2hr. 後端考官 C (應該是主管) 一樣先自我介紹, 接著主考官會針對你履歷中的經歷做詢問  (印象中這關技術面問得比較少, 詢問內容比較 focus 在你的背景, 未來興趣 ... 這些) 不過最後也是 Synology 必考的程式題, 題目是 Validate Palindrome 寫完後會接著延伸是問如何找出 Longest Palindrome 我寫出 Expand Around Center 的解法後主管又做了一些變形引導你寫 DP 解 原本以為要結束了, 考官最後又多出...
閱讀完整內容

[面試心得] VICI Holdings / 威旭(高頻交易) - Software Engineer

-
  零面. 作業   作業很簡單，寫一個計算日期A到日期B之間有多少天數的程式。 一面. 現場 先考筆試，筆試題目類型很廣 (如 Pointer, Sizeof, Structure padding, cache line, race condition ...)， 筆試寫完之後接著就是技術面談， 詢問我之前在聯發科做的一些題目，例如: 如何讓效能提升好幾倍? 然後接著有介紹一下公司在做甚麼 (主要是在做高頻交易，需要接交易所 API)， 另外也有介紹到公司有一些 team 是在做 FPGA 跟網卡 Driver ... 等，用來降低交易延遲。 技術面談完之後，接著就是 HR 進來詢問我有沒有什麼問題之類的， 但不得不說我對整場面試的經驗蠻差的，原因是: 1.  零面的作業我覺得題目很沒意義 ...  2. 考了筆試卻完全沒問筆試內容，這樣筆試是在寫好玩的嗎 ... 3. 本來 HR 是找我面資深，結果說是年資不夠改成非資深的缺，我頗無言的是資深的年資說要 8 年 ...，意味者在裡面的工程師要待 8 年才能升等，中間都沒其他職等? 而且詢問 HR他們想要的資深人員的條件是啥，但也說得不清不楚 ... 4. 詢問 HR 很多關於公司制度面的事情，但 HR 好像是新來的，都不太了解 以上除了第四點我都有跟 HR 反應，HR 表示我狀況比較特別 (痾 其實3年經驗的人應該很多吧...)，會再跟主官討論看看這樣。 結果: Offer Get，福利忘了但我記得不優 (應該是比照勞基法)，83 K * 14 ~ 18 (HR 說法是每年獎金至少會有 2 個月，所以可當成 16 來看)，另外薪資部分應該可以再談，但我確定沒要去這間就沒談了
閱讀完整內容

[面試心得] GoFreight / 聖學科技(Freight Forwarder) - Full-Stack Engineer

-
零面. Hacker Rank (120 min) 5 題 Hacker Rank，難度約 2 題 Easy 2 題 Medium 1題 Hard， 第 1 題: 算 duplicate 個數，解法: Hash Table O(1) 第 2 題: Smallest window that contains all characters of string itself，解法: Sliding window O(n) 第 3 題: Sort 之後取前 n 大加總 (英文閱讀測驗? )，解法: std::sort O(n log n) 第 4 題: Minimum increment to make array unique，解法: sort O(n log n) 第 5 題: Connected component，解法: DFS O(|V| + |E|) 運氣算蠻好的，Hard 那題感覺實際只有到 Medium 而已，Medium 的也都算簡單， 全部寫完還有約 40 ~ 50 分鐘，網站測資都有過，不知道實際分數就是了 XD 一面. 遠端 第一場 1hr. 1 位考官 這關是純白版題，估計是怕有人 Hacker Rank 找代打 XD  題目是四則運算，輸入 3 + 5 * 4 的字串 (無括號)，輸出 23， 看到題目很直覺告訴考官是後序，但尷尬的是老早忘記細節怎麼做 ... 冏 於是考官請我先不要管後序，想先看看我撇開前中後序下會怎麼寫， 於是就先使用直覺的方法做出一個很醜的演算法， 接著考官又加入括號問我要怎麼做，原本想繼續用很醜的方法寫， 但寫一寫發現括號會遇到的問題比較麻煩，最後就回想後序做法，最後用後序完成 ~ 第二場 2hr. 1 位考官 (應該是技術長?) 這關就不再考算法了，先自我介紹之後針對履歷開始逐一詢問， 除了針對履歷外也詢問了很多 GoFreight 會用到的技能， 如: Python2/3 差異 (range, list/tuple, unicode ... 等)，Hash 碰撞如何處理，Browser 瀏覽網頁時整個 request 的流程 (load balancer, nginx ... 等)，js 放在 header / body 差異 ... 等等， 不得不說考的內容蠻詳細的，也會針對你提出的解法做...
閱讀完整內容