leetcode:299二叉树的右视图

发布于:2024-11-29 ⋅ 阅读:(21) ⋅ 点赞:(0)

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

示例 1:

输入:root = [1,2,3,null,5,null,4]

输出:[1,3,4]

解释:

示例 2:

输入:root = [1,2,3,4,null,null,null,5]

输出:[1,3,4,5]

解释:

示例 3:

输入:root = [1,null,3]

输出:[1,3]

示例 4:

输入:root = []

输出:[]

提示:

  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100 

步骤 1:问题定义与分析

题目要求: 给定一个二叉树的根节点 root,返回从树的右侧所能看到的节点值。我们需要按层从上到下列出这些节点。

输入输出条件

  • 输入
    • 一个二叉树的根节点 root,表示一个二叉树。
    • 二叉树的节点个数范围是 [0, 100]
    • 节点值范围是 -100 <= Node.val <= 100
  • 输出
    • 返回一个数组,包含从右侧看到的节点值,按从上到下的顺序排列。

潜在边界条件

  1. 空树:当 rootnull 时,二叉树为空,返回空数组。
  2. 只有一个节点:二叉树只有根节点时,返回该节点。
  3. 不平衡树:有的树可能比较不平衡,右侧看到的节点顺序和层数都可能比较复杂。

步骤 2:分解问题与解题思路

问题分析:
  1. 从“右侧视角”看,意味着我们需要按从右到左的顺序记录每一层的第一个节点。
  2. 层次遍历可以帮我们逐层查看每个节点,但需要保证按右侧顺序访问。
解决方案:

可以通过两种主要方法来解决此问题:

  1. 广度优先搜索(BFS):使用队列进行层次遍历。每一层我们只记录最右边的节点。
  2. 深度优先搜索(DFS):通过递归的方式,优先访问右子树,确保每一层最右边的节点先被访问。

对于这类问题,DFS 更加简洁且高效,因为它不需要显式地维护队列,并且通过控制递归的顺序能够更自然地满足“从右侧看到节点”的要求。

步骤分解:
  • DFS 递归方案
    1. 初始化一个空数组 ans 来存储结果。
    2. 从根节点开始,递归遍历二叉树。
    3. 每次递归进入新的一层时,判断该层是否已经访问过(通过判断 depth == ans.size()),如果是第一次访问该层,则记录当前节点的值。
    4. 优先递归右子树,然后递归左子树。
    5. 返回结果数组 ans
时间与空间复杂度:
  • 时间复杂度O(n),每个节点都只访问一次。
  • 空间复杂度O(h),其中 h 是树的高度。递归栈的深度与树的高度有关,最坏情况下,树可能是链状的,空间复杂度为 O(n)

步骤 3:C++ 代码实现

代码解析:

  1. dfs 函数
    • 每次递归进入一个节点时,如果当前深度 depth 是第一次访问,则将该节点的值加入结果数组 ans
    • 在递归过程中,优先访问右子树,确保从右侧看到的节点先被记录。
  2. rightSideView 函数
    • 这是主函数,调用 dfs 来遍历整个树,并返回最终的右侧视图。

步骤 4:通过解决问题获得的启发

从这个问题中我们可以获得以下几个启发:

  1. 递归优先级控制:递归的顺序可以显著影响最终的结果。在这类“视角问题”中,通过控制访问顺序(如优先访问右子树),能够实现更高效的结果。
  2. 树的遍历技巧:通过深度优先搜索(DFS)和广度优先搜索(BFS)两种方式,我们可以灵活地应对树形结构的遍历问题,DFS 在这类视角问题中往往更直观,且代码简洁。
  3. 空间优化:通过递归方式,我们可以避免使用额外的队列存储中间节点,从而节省空间。

步骤 5:算法在实际生活中的应用

实际应用场景:

  1. 图像处理与计算机视觉

    • 应用:在计算机视觉中,我们经常需要对图像中的结构进行分析,尤其是在多层结构中。假设我们有一个图像金字塔结构,类似于树的结构,算法可以帮助识别从某一侧看到的物体。
    • 具体实现:在进行图像处理时,我们可以构建一个多层的图像金字塔,每一层代表图像的不同分辨率。从右侧(即从视角上最右边的像素)来观察图像,可以帮助我们定位和优化图像分析的处理路径。
  2. 游戏开发中的视角计算

    • 应用:在一些策略游戏或角色扮演游戏(RPG)中,玩家的视角往往限制在一个特定的区域内。对于这种情况,算法可以用于优化视野计算,判断玩家能够看到哪些对象或障碍物。
    • 具体实现:假设游戏中存在一个动态的障碍物树状结构,算法可以帮助确定玩家从右侧视角能够看到的所有物体,从而优化图形渲染和交互逻辑。
  3. 机器人导航与避障

    • 应用:在机器人导航中,如何计算机器人从某个特定方向的可视区域至关重要。类似的算法可以用于机器人规划路径时避开障碍物。
    • 具体实现:通过使用树形结构来模拟机器人周围环境的地图,结合右侧视角计算,可以帮助机器人更高效地感知环境并避开障碍物。

通过这些应用,我们可以将该算法有效地应用到实际的图形处理、机器人规划、甚至游戏开发等多个领域。