---
# System prepended metadata

title: '**Leetcode筆記(Binary Tree Right Side View)**'
tags: [medium, binary tree, leetcode]

---

# **Leetcode筆記(Binary Tree Right Side View)**


:::info
:information_source: 題目 : Binary Tree Right Side View, 類型 : binary tree , 等級 : medium
日期 : 2023/05/23，2023/07/05，2023/09/13，2024/09/04
:::


### 嘗試
2023/07/05
每次都用tmp去紀錄最尾端的是誰
記得要用popleft
```python
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return None
        res = []
        q = deque([root])
        while q:
            for _ in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                tmp = node.val
            res.append(tmp)
        
        return res
```
2023/09/13
```python
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return None

        res = []
        q = deque([root])
        while q:
            length = len(q)
            for _ in range(length):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                lastnode = node
            res.append(lastnode.val)
        
        return res
```
2024/09/04
```python
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return None

        res = []
        q = deque()
        q.append(root)

        while q:
            length = len(q)
            for _ in range(length):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                temp = node.val
            res.append(temp)
        
        return res
```


---
### **優化**

時間複雜度是 O(n)，在最壞的情況下，我們需要遍歷每個節點一次，並將其放入佇列中。
空間複雜度也是 O(n)，其中 n 是二叉樹中的節點數量。在佇列的過程中，最壞的情況下，佇列中可能存儲著二叉樹的所有節點，佔用 O(n) 的額外空間。

```python
# bfs queue
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return None
        q = deque([root])
        res = []

        while q:
            # 每次都把最右的拿出來
            res.append(q[-1].val)
            for _ in range(len(q)):
                # 但也不會失去append整個樹的機會
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        
        return res
```
```python
# bfs 遞迴
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # len([[1]])為1 / len([[1], [2]])為2
        # [].append([])結果為[[]] 長度為1
        res = []

        def bfs(node, level, res):
            if not node:
                return
            # 創造空儲存集
            if len(res) == level:
                res.append([])
            res[level].append(node.val)
            bfs(node.left, level + 1, res)
            bfs(node.right, level + 1, res)

        bfs(root, 0, res)

        return [res[l][-1] for l in range(len(res))]
```
---


**:warning: 錯誤語法** 
:::warning

:::


**:thumbsup:學習** 
:::success

:::

**思路**


**講解連結**
https://blog.csdn.net/fuxuemingzhu/article/details/79557632
Provided by. 负雪明烛

###### tags: `binary tree` `medium` `leetcode`