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可以按层序遍历二叉树。
广度优先搜索法
- 解题思路：
LeetCode 上的题目 “二叉树的右视图” 要求我们从二叉树的右侧观察，打印出每一层的最后一个节点的值。这个问题可以通过多种方法解决，但最常用的是使用广度优先搜索（BFS）算法。执行广度优先搜索，左结点排在右结点之前，这样，我们对每一层都从左到右访问。因此，只保留每个深度最后访问的结点，我们就可以在遍历完整棵树后得到每个深度最右的结点。
以下是解题思路的步骤：
理解问题：首先，明确题目要求我们打印出二叉树每层的最后一个节点的值。
使用队列：由于我们需要逐层访问节点，队列是实现这一目标的理想数据结构。
初始化：
- 创建一个队列
queue来存储当前层的节点。- 创建一个列表
result来存储每层的最后一个节点的值。BFS 遍历：
- 将根节点加入队列。
- 当队列不为空时，进行循环：
- 记录当前层的节点数量，例如
level_size。- 迭代
level_size次，每次从队列中取出一个节点：
- 如果是当前层的最后一个节点（即
queue中没有其他节点），则将其值添加到result中。- 将当前节点的右子节点（如果有的话）加入队列。
- 如果当前节点有左子节点，先将其加入队列，然后再处理右子节点，以确保右视图的顺序。
返回结果：遍历结束后，
result列表将包含每层的最后一个节点的值，返回这个列表。注意：在处理节点时，如果节点为
None，则忽略它。代码实现：根据上述思路，使用适当的编程语言实现算法。
- 复杂度：时间复杂度为，空间复杂度为。
- 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
- 代码仓库地址：rightSideView