题目描述

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

示例

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

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

解答方法

方法一：广度优先搜索

思路

从上至下一层一层遍历二叉树，每层从左至右遍历当前层所有节点，将每个节点的子节点储存起来作为下一层要遍历的节点，将当前层的最后一个节点的值添加至最终结果，直到所有层遍历完毕

代码

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        result = []
        temp_layer = [root]
        while temp_layer:
            next_layer=[]
            for i in temp_layer:
                if i.left:
                    next_layer.append(i.left)
                if i.right:
                    next_layer.append(i.right)
            result.append(temp_layer[-1].val)
            temp_layer = next_layer
        return result

时间复杂度

O(n)

空间复杂度

空间复杂度 : O(n)。由于广度优先搜索逐层访问整棵树，在访问最大的层之前，队列将最大。该层最坏的情况下可能有 0.5n=O(n) 大小（一棵完整的二叉树）。