# **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

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

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

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) 的額外空間。

# 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

# 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`