前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >​LeetCode刷题实战199:二叉树的右视图

​LeetCode刷题实战199:二叉树的右视图

作者头像
程序员小猿
发布2021-03-04 14:24:08
2320
发布2021-03-04 14:24:08
举报
文章被收录于专栏:程序IT圈

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 二叉树的右视图,我们先来看题面:

https://leetcode-cn.com/problems/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.

题意

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

示例

解题

https://www.imooc.com/article/303711

思路一:广度优化搜索

当对二叉树进行层次遍历时,每一层最右边的节点是最后访问的。题目中要求返回从右侧所能看到的节点值,正是这里每层最右边的节点。那么保留每层最后的访问节点,就能得到需要求的答案。

这里使用队列存储。

具体可参照代码进行理解。

代码语言:javascript
复制
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if root == None:
            return []
        # 导入 deque 创建队列
        from collections import deque

        queue = deque([root])

        res = []

        while queue:
            size = len(queue)
            # 这里用 size 记录二叉树每层的节点数,
            for i in range(size):
                # 弹出节点
                node = queue.popleft()
                # 先将左节点入队
                if node.left != None:
                    queue.append(node.left)
                # 再将右节点入队
                if node.right != None:
                    queue.append(node.right)
                # 队列先入先出,如果 i 等于 size - 1,
                # 那么这里就是最右边的节点,这个就要得到的结果,将其放入返回列表中
                if i == size - 1:
                    res.append(node.val)

        return res
思路二:深度优化搜索

同样的,这道题也能够使用深度优化搜索来解决。

在搜索的过程中,我们先访问右子树,再访问左子树。那么每层的第一个节点就是最右边节点。这个时候,只要知道二叉树的深度,则可以得到最终的答案。

具体可参照代码进行理解。

代码语言:javascript
复制
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        res = []

        def _dfs(node, depth):
            if node == None:
                return []

            # res 的索引表示二叉树的深度
            # 若当前的深度的节点不存在于 res 中,
            # 表示该层的最右边节点还未将其添加到 res 中
            # 将其加入到节点中
            if depth == len(res):
                res.append(node.val)
            # 往一下层访问,先访问右子树,在访问左子树
            depth += 1

            _dfs(node.right, depth)
            _dfs(node.left, depth)

        _dfs(root, 0)

        return res

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-03-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员小猿 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意
  • 示例
  • 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档