199. 二叉树的右视图

题目

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

提示:

• 二叉树的节点个数的范围是 [0,100]
• -100 <= Node.val <= 100

解答

思路

由于是右视图，因此我们考虑先递归右子树（例如示例一中，先递归右子树，1 后面就是 3，而不是 2）现在有两个问题：如何记录答案？如何判断这个节点是否需要记录到答案中？我们可以考虑每个 节点的深度，显然 2, 3 的深度都是 2，但是由于先遍历的右子树，因此 3 先记录到答案中，所以 2（节点深度为 2 的所有结点）会被挡住，不记录到答案中。

• 时间复杂度为 $O(n)$
• 空间复杂度为 $O(n)$

代码

Python 代码

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        
        def f(node, depth):
            if node is None:
                return 
            
            if depth == len(ans): # 加入后，ans 的长度自动 + 1
                ans.append(node.val)
            
            f(node.right, depth + 1)
            f(node.left, depth + 1)
        
        f(root, 0)
        
        return ans