0199. Binary Tree Right Side View - chasel2361/leetcode GitHub Wiki

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

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

Example 2:
Input: root = [1,null,3]
Output: [1,3]

個人覺得這題最難的是看不懂題目XD
其實意思就是要你從側面來看二元數，列出每層最右邊的元素值，就降。

所以可以用BFS來解，跟 1161. Maximum Level Sum of a Binary Tree 一樣
把每一層所有的節點都丟進 deque 裡，再找到最右邊的節點取值存入 list，最後輸出就可以惹

from collections import deque

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if not root:
            return res
        
        q = deque([root,])
        while q:
            cnt = len(q)
            for _ in range(cnt):
                ptr = q.popleft()
                if ptr.left:
                    q.append(ptr.left)
                if ptr.right:
                    q.append(ptr.right)
            res.append(ptr.val)
        return res

這樣解的話時間跟空間複雜度都是 O(N)，因為要把整棵樹都走一遍，而且最糟糕的狀況是 deque 存入的節點數與總結點數為同一次方級。

---

看了大神的寫法，發現可以把上面的程式優化如下

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if root:
            level = [root]
            while level:
                res += [level[-1].val]
                level = [kid for node in level for kid in [node.left, node.right] if kid]
        return res

邏輯一樣，但更精簡了