一題多解 二元樹的右側視角Binary Tree Right Side View_Leetcode #199_精選75題
題目敘述
題目會給我們一顆二元樹的根結點，請我們列出每一層最右邊的節點值，以陣列的形式返回答案。
測試範例
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
每一層最右邊的節點值分別是1, 3, 4
Example 2:
Input: root = [1,null,3]
Output: [1,3]
每一層最右邊的節點值分別是1, 3
Example 3:
Input: root = []
Output: []
空樹，回傳空陣列即可。
約束條件
Constraints:
- The number of nodes in the tree is in the range
[0, 100].
節點總數介於0 ~ 100之間。
所以實作時要留意一個小細節，邊界條件的處理，題目可能會給我們一顆空樹喔!
-100 <= Node.val <= 100
節點值介於-100 ~ 100之間。
演算法 BFS
其實解題線索就藏在題目裡了!
題目說請我們想像站在這顆樹的右邊，看看這個樹，列出每一層最右邊的節點。
關鍵字是"每一層"，那很自然就會聯想到逐層遍歷的Level-order traversal，或者說
我們把樹視為一張圖Graph，從root node開始由上往下逐層拜訪整顆樹。
根據題意的需求，我們只要每層都保持由右向左訪問順序，很自然，每一層的第一顆節點就是我們所需要的Right side view nodes，右側視角的節點，把節點值依序記錄下來，以陣列的形式回傳答案即可。
image.png
程式碼 BFS
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
# Quick response on empty tree
if not root:
return []
# Starting point is root node
bfs_q = deque([root])
view = []
# Launch level-order traversal from right-hand side to left-hand side
while bfs_q:
# First node on current level is the node of right-side view
view.append( bfs_q[0].val )
# Add child node from right to left
for _ in range( len(bfs_q) ):
cur = bfs_q.popleft()
cur.right and bfs_q.append( cur.right)
cur.left and bfs_q.append( cur.left)
return view
複雜度分析 BFS
令n=節點總數目
時間複雜度:
從根結點開始拜訪整棵樹，每個節點至多訪問一次，總共所需時間為O(n)。
空間複雜度:
BFS queue的長度，每個節點至多訪問一次，總共所需空間為O(n)。
演算法 DFS
還有另一種解法，用深度優先也可以。
題目說請我們想像站在這顆樹的右邊，看看這個樹，列出每一層最右邊的節點。
根據題意的需求，我們只要每一層DFS都保持由右向左訪問順序，先走訪問右子樹，再訪問左子樹，很自然，每一層的第一顆節點就是我們所需要的Right side view nodes，右側視角的節點，把節點值依序記錄下來，以陣列的形式回傳答案即可。
程式碼 DFS
from collections import defaultdict
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if not root:
# Quick response for empty tree
return []
# key: depth
# value: value of right-most node
self.side_view_dict = defaultdict( int )
self.max_depth = 0
def helper( node: TreeNode, depth: int):
if node:
if self.side_view_dict.get(depth, None) == None:
self.side_view_dict[depth] = node.val
self.max_depth = max( self.max_depth, depth)
# Let right sub-tree go before left sub-tree in order to get right side view
helper( node.right, depth+1 )
helper( node.left, depth+1 )
# ----------------------------------------
helper( node = root, depth = 0 )
return [ self.side_view_dict[depth] for depth in range(0, self.max_depth+1) ]
複雜度分析 DFS
令n=節點總數目
時間複雜度:
從根結點開始拜訪整棵樹，每個節點至多訪問一次，總共所需時間為O(n)。
空間複雜度:
DFS recursion stack的深度，每個節點至多訪問一次，總共所需空間為O(n)。
關鍵知識點
條條大路通羅馬，只要掌握基本原理，遇到新的題目也能根據基本的圖論演算法DFS、BFS配合題意的需求去構建出解題的演算法。
另外，還有一個衍伸題，假如題目問我們左側視角 Left side view? 要怎麼改?
也很容易，把拜訪順序改成從左到右，取每一層第一個遇到的節點值，就可以囉！
Reference:
