今天我們來加深對樹的遞迴思想的理解。

題目連結: 199. Binary Tree Right Side View

題目描述:給定一棵二元樹的根節點 root，想像你自己站在它的右側，按照從頂部到底部的順序，返回你能看到的節點的值。

Input: root = [1,2,3,null,5,null,4]

Output: [1,3,4]

Input: root = [1,2,3,4,null,null,null,5]

Output: [1,3,4,5]

Python

解題思路:
這道題可以使用BFS、DFS來實現，BFS方法是使用queue方式,DFS則是使用遞歸的方式做處理。

我自己是使用(根 -> 右 -> 左)順序的DFS演算法來解這道題(個人覺得相對容易)。

因為是要判斷最右邊的值，只要先計算當前深度與答案長度是否相等，就可以把答案加入陣列中。

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans =[]
        def dfs(node,depth):
            if node == None:
                return
            if depth == len(ans):
                ans.append(node.val)
            dfs(node.right,depth+1)
            dfs(node.left,depth+1)
        dfs(root,0)
        return ans

演算法分析:

• dfs(node.right,depth+1)
     dfs(node.left,depth+1)，這部分是優先遍歷右子樹，確保了在任何一個depth，我們的演算法總是優先訪問最右邊的節點。
• if depth == len(ans):直觀意思是「我們是不是第一次到達 depth 這個深度？」
• 因為我們總是優先訪問右邊的節點，所以第一次到達某個深度的節點，必然就是該層最右邊的、我們能從右邊看到的那個節點。一旦這個節點被加入 ans 列表，len(ans) 就會增加，同一層的其他（更左邊的）節點在後續訪問時，就不會再滿足 depth == len(ans) 這個條件了。

複雜度分析:

• 時間複雜度為 O(n)(我們需要遍歷樹中的每一個節點一次，n 是樹的總節點數)。
• 空間複雜度： O(n)。
  1. 空間消耗主要來自於遞迴呼叫的堆疊 。
  2. 堆疊的深度取決於樹的高度n。
  3. 平均情況（樹是Avg Tree），空間複雜度是 O(log n)。
  4. 最壞情況（樹極度不平衡，退化成鏈結串列），空間複雜度是 O(n)。

有問題可以底下留言!
下回見!!