2024-01-26|閱讀時間 ‧ 約 9 分鐘

一題多解 二元樹的右側視角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:

[1] Binary right side view by DFS // BFS

分享至
成為作者繼續創作的動力吧!
從 Google News 追蹤更多 vocus 的最新精選內容從 Google News 追蹤更多 vocus 的最新精選內容

小松鼠的演算法樂園 的其他內容

你可能也想看

發表回應

成為會員 後即可發表留言
© 2024 vocus All rights reserved.