1 題目描述

假如你站在樹的右邊，看著樹，你會看到樹的右邊的節點。紀錄下來這些節點。

2 解法

一開始我看到這題的時候，腦子浮現的是，我就是努力的往右邊走，如果右邊沒辦法走了，就往左邊走，這樣就可以記錄下來右邊的節點了。但是我的想法無法解決以下這個情境：

以下的程式碼是錯誤的，他只會記錄到right subtree的最右邊，但是left subtree也就是 2 跟 5 節點不會被尋訪。

class Solution:
    res = []
    def rightSideView(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        if root: 
            self.res.append(root.val)
        # 如果右邊有節點，就往右邊走
        if root.right:
            self.rightSideView(root.right)
        # 如果右邊沒有節點，但左邊有，就往左邊走
        elif root.left: 
            self.rightSideView(root.left)
        return self.res

因此我們希望，當發現右邊已經走到底時，但是左邊的高度比較高時，我們還是要繼續往left subtree走，這樣才能記錄到左邊的節點。他的關鍵在，回傳的答案會與樹的高度有關。我們需要有兩個思維：

如果右邊可以走，優先走右邊，並且把最右邊的節點記錄下來。
如果發現右邊已經觸底了，那就換左樹走，但是左樹也不是每個最右邊的節點都要記錄，只有當高度比右樹高時，才要記錄。

def rightSideView(self, root: TreeNode) -> List[int]:
    def helper(node, depth): 
        if node:
            # 只有如果目前的高度與答案的長度相等時，才要記錄
            if depth == len(ans):
                ans.append(node.val)
            # 右邊繼續往下走，depth + 1
            helper(node.right, depth + 1)
            # 左邊繼續往下走，depth + 1
            helper(node.left, depth + 1)

    ans = []
    helper(root, 0)
    return ans

也可以用BFS的方式來解這題，我們可以用queue來記錄每一層的節點，並且每次只記錄每一層的最右邊的節點。

def rightSideView(self, root: TreeNode) -> List[int]:
    if not root:
        return []
    res = []
    queue = deque([root])
    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.popleft()
            if i == size - 1:
                res.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return res