leetcode：299二叉树的右视图

给定一个二叉树的 根节点 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. 空树：当 root 为 null 时，二叉树为空，返回空数组。
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. 机器人导航与避障：

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

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