请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

199. 二叉树的右视图 Python

2023-07-13


一、题目描述

给定一个二叉树的 根节点 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

二、代码

代码如下:

# 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 = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        result = []
        # 最开始的一层中只有根节点一个节点
        cur = [root]
        while cur:
            next = []
            path = []
            for node in cur:
                # path 用于存储这一层所有的结点值
                path.append(node.val)
                # 如果当前节点有左子树
                if node.left:
                    # 则在下一层需要遍历的结点数组中添加
                    next.append(node.left)
                # 如果当前节点有右子树
                if node.right:
                    next.append(node.right)
            # 让当前遍历的结点数组更新为下一次遍历的结点数组,即下一层所有结点的数组
            cur = next
            # 只添加层序遍历中每一层的最后一个节点值
            result.append(path[-1])

        print(result)
        return result

三、解题思路

本题实际上是考察二叉树的层序遍历,与二叉树的层序遍历不同的是,本题只需要将每一层的最后一个节点存入即可。关于二叉树的遍历可以参考 102. 二叉树的层序遍历 Python

相关阅读

手机版|MSIPO技术圈 皖ICP备19022944号-2

Copyright © 2024, msipo.com

返回顶部