0199. Binary Tree Right Side View (Medium)

另外筆者昨天生日，快補祝我生日快樂XDDDDD

Question

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

1
2
3

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

1
2
3
4
5

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

分析/解題

給定一棵二元樹，想像你站在樹的右邊往左看，
試回傳從上到下依序所看到的值。

這題一看就知道某種程度上屬於level-order traversal，
(還不清楚或不知道什麼是level-order的讀者請參閱這篇)
只是要求的部分有點不一樣而已，這邊只要求最右邊的數字。

那麼要注意囉！可能會有人想，我能不能只走最右邊 取值就好呢？
答案是當然不行！！！因為你可能會遇到類似這樣的狀況：

你看到的最右邊不是人家的最右邊XD

如果只取最右邊的話，顯然我們會走1-3-0然後就結束了，
但還有一個4落在中間，所以這題無論如何還是要乖乖遍歷所有節點才行。

我們可以用BFS的方式來解這題(DFS也行，但要用到遞迴，這裡暫不討論)，步驟如下：

1. 先新增一個queue用來存放當層(level)的所有節點，
   另外開一個串列res(result)用來存放結果。
2. 記錄當下queue的總數cnt(count)。
3. 執行一個cnt次數的迴圈，依序將當層的節點取出
4. 每取出一個節點，就分別檢查其左右節點是否存在，
   存在則以先左後右 的順序放入queue中。
5. 迴圈執行完後，queue中應該全是下一層的節點；
   同時最後一個取出的節點 ，就是每層最右邊的節點，
   將其值取出放入res中。
6. 重複2~5的動作，直到queue中沒有節點為止。

讀者會發現這樣的做法唯一的差別就是要記錄最後一個取出的節點 ，
其他和level-order traversal一樣，利用queue先進先出的原則，
每次恰好處理一層的節點。

依此我們可以寫成程式碼，
Java的部分List和Queue都可以使用LinkedList，
且TreeNode的部分由於Java必須給定值，故一開始last先行給定為null。

Java

Python的部分不要忘記當需要從左邊取值時deque 的速度會較List快，
另外last其實可以不用先給值也可以順利通過。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N), O(N)，每個節點都會遍歷過，
同時因為使用Queue的時候中間會儲存整個level，
空間複雜度還是跟總數相關。)

「可以使用DFS嗎？」
(可以，但需要對每項記錄其level，解法相對較難處理，讀者可嘗試看看)

「如果題目改成從左邊看呢？」
(一樣要遍歷所有節點，但改成在每一層的第一項就將值置入到答案中)

相似及延伸

1.0102. Binary Tree Level Order Traversal

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~