1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」—— 199. 二叉树的右视图

flypython • • leetcode题解

199. 二叉树的右视图

链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/
难度：中等

题目

点击原文链接跳转查看题目

思路

站在二叉树的右侧，从顶部到底部，那么从上到下，看到的就是第一层的右结点，然后是第二层的右结点，这样一直下去。这题我们只需要BFS或者DFS变一下就可以解决。

首先，我们需要层次遍历，对于每一层来说，最右结点是最后遍历到的。那我们只需要树的时候，只保留每一层最右结点就可以。在这里我们用队列来存储数据。

最后，代码见解决方案。

方案代码

解决方案：

from collections import deque
class Solution(object):
    def rightSideView(self, root):
        rightmost_value_at_depth = dict() # 深度为索引，存放节点的值
        max_depth = -1
        queue = deque([(root, 0)])
        while queue:
            node, depth = queue.popleft()
            if node is not None:
                # 维护二叉树的最大深度
                max_depth = max(max_depth, depth)
                # 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
                rightmost_value_at_depth[depth] = node.val
                queue.append((node.left, depth+1))
                queue.append((node.right, depth+1))
        return [rightmost_value_at_depth[depth] for depth in range(max_depth+1)]

原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/345.html

赞 (0)
flypythonflypython
0 0 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
« 上一篇 21/04/2020 11:01
下一篇 » 23/04/2020 11:03

相关推荐