LeetCode 算法：二叉树的右视图 c++

原题链接🔗：二叉树的右视图
难度：中等⭐️⭐️

题目

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

题解

二叉树

• 二叉树是一种基本的树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树的特点是每个节点的左子节点的值小于或等于该节点的值，而右子节点的值大于或等于该节点的值。这种特性使得二叉树非常适合用于排序和搜索操作。

二叉树右视图

• 二叉树的右视图问题通常指的是从二叉树的右侧观察，获取从上到下每一层最右边的节点值。这个问题可以通过广度优先搜索（BFS）算法来解决，因为BFS可以按层序遍历二叉树。

广度优先搜索法

1. 解题思路：

LeetCode 上的题目 “二叉树的右视图” 要求我们从二叉树的右侧观察，打印出每一层的最后一个节点的值。这个问题可以通过多种方法解决，但最常用的是使用广度优先搜索（BFS）算法。执行广度优先搜索，左结点排在右结点之前，这样，我们对每一层都从左到右访问。因此，只保留每个深度最后访问的结点，我们就可以在遍历完整棵树后得到每个深度最右的结点。

以下是解题思路的步骤：

1. 理解问题：首先，明确题目要求我们打印出二叉树每层的最后一个节点的值。

2. 使用队列：由于我们需要逐层访问节点，队列是实现这一目标的理想数据结构。

3. 初始化：

   • 创建一个队列 queue 来存储当前层的节点。
   • 创建一个列表 result 来存储每层的最后一个节点的值。

4. BFS 遍历：

   • 将根节点加入队列。
   • 当队列不为空时，进行循环：
     • 记录当前层的节点数量，例如 level_size。
     • 迭代 level_size 次，每次从队列中取出一个节点：
       • 如果是当前层的最后一个节点（即 queue 中没有其他节点），则将其值添加到 result 中。
       • 将当前节点的右子节点（如果有的话）加入队列。
       • 如果当前节点有左子节点，先将其加入队列，然后再处理右子节点，以确保右视图的顺序。

5. 返回结果：遍历结束后，result 列表将包含每层的最后一个节点的值，返回这个列表。

6. 注意：在处理节点时，如果节点为 None，则忽略它。

7. 代码实现：根据上述思路，使用适当的编程语言实现算法。

2. 复杂度：时间复杂度为，空间复杂度为。
3. c++ demo：

#include <iostream>
#include <vector>
#include <queue>// 定义二叉树的节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class Solution {
public:// 函数用于获取二叉树的右视图std::vector<int> rightSideView(TreeNode* root) {std::vector<int> result;if (!root) return result;std::queue<TreeNode*> q;q.push(root);while (!q.empty()) {int levelSize = q.size(); // 当前层的节点数量for (int i = 0; i < levelSize; ++i) {TreeNode* node = q.front();q.pop();// 如果是当前层的最后一个节点，添加到结果中if (i == levelSize - 1) {result.push_back(node->val);}// 将左子节点入队（如果有的话）if (node->left) q.push(node->left);// 将右子节点入队（如果有的话）if (node->right) q.push(node->right);}}return result;}
};int main() {// 创建一个示例二叉树//       1//      / \//     2   3//    / \   \//   4   5   6TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);root->right->right = new TreeNode(6);Solution solution;std::vector<int> rightView = solution.rightSideView(root);// 打印右视图结果for (int val : rightView) {std::cout << val << " ";}std::cout << std::endl;// 释放二叉树内存（这里简化了释放过程，实际中需要递归释放所有节点）delete root->left->left;delete root->left->right;delete root->left;delete root->right->right;delete root->right;delete root;return 0;
}

• 输出结果：

1 3 6

3. 代码仓库地址：rightSideView