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   6
    TreeNode* 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;
}