【广度优先搜索】199.二叉树的右视图
DayNightStudy
2021-01-30 23:10
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目解析
找到 树 右视图，需要做的操作：
首先需要找到 每一层最右边的值；
这些值的 集合 即为 答案
题目解答
方法：层次遍历的 非递归方法
思路：
利用 层层次遍历的 非递归方法 遍历 每一层
保存每一层 的 最右边一个元素；
最后这些值的 集合即为 答案
代码展示
# 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 = rightclass Solution:def rightSideView(self, root: TreeNode) -> List[int]:'''方法：队列迭代 (非递归)'''res = []if not root:return resqueue = collections.deque()queue.append(root)while queue:last = -999for i in range(len(queue)):node = queue.popleft()last = node.valif node.left:queue.append(node.left)if node.right:queue.append(node.right)res.append(last)return res
复杂度计算
时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。
-空间复杂度：O(N)，当树为平衡二叉树时，最多有N/2个树节点入队，使用 O(N) 大小的额外空间
运行结果
评论