算法: 二叉树右侧视图199. Binary Tree Right Side View

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]

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

DFS 深度优先解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def dfs(node, depth, res):
            if not node: return
            if depth == len(res):
                res.append(node.val)
            dfs(node.right, depth+1, res)
            dfs(node.left, depth+1, res)
        dfs(root, 0, res)
        return res

BFS 广度优先算法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        res = []
        level = [root]
        while level:
            res.append(level[-1].val) # res += level[-1].val,
            level = [kid for node in level for kid in (node.left, node.right) if kid]
        return res

参考

https://leetcode.com/problems/binary-tree-right-side-view/discuss/56064/5-9-Lines-Python-48%2B-ms