一題多解 二元樹的右側視角Binary Tree Right Side View_Leetcode #199_精選75題

Raychan null on Unsplash

題目敘述

題目會給我們一顆二元樹的根結點，請我們列出每一層最右邊的節點值，以陣列的形式返回答案。

題目的原文敘述

測試範例

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