01、二叉树的右视图

题目链接：199. 二叉树的右视图 - 力扣（LeetCode）

哈喽，大家好，我是厨子，今天继续来给大家讲一个有趣的题目，二叉树的右视图

题目描述

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

示例 1：

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

        1      <--- 看到 1
       / \
      2   3    <--- 看到 3
       \   \
        5   4  <--- 看到 4

示例 2：

输入：root = [1,null,3]
输出：[1,3]

        1      <--- 看到 1
         \
          3    <--- 看到 3

示例 3：

输入：root = []
输出：[]

数据范围：

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

题目分析

这道题的关键是理解"右视图"的含义：**每一层最右边的节点，**从右侧看二叉树，每层只能看到最右边的那个节点。

解题思路

这个题目最方便的解题方式就是层序遍历，遍历每一层，取每层的最后一个节点

BFS（层序遍历）

1. 使用队列进行层序遍历

2. 遍历每一层时，记录该层的最后一个节点

3. 将所有层的最后一个节点加入结果

图解过程

以 root = [1,2,3,null,5,null,4] 为例：

        1
       / \
      2   3
       \   \
        5   4

第 1 层：[1]           → 最右节点：1
第 2 层：[2, 3]        → 最右节点：3
第 3 层：[5, 4]        → 最右节点：4

结果：[1, 3, 4]

C++ 实现

#include <vector>
#include <queue>
using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;

        // 特殊情况：空树
        if (root == nullptr) {
            return result;
        }

        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;
    }
};

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。

空间复杂度：O(n)。队列中最多存储一层的节点。

BFS 优化版

算法思路

每层只需要记录最右边的节点，可以在遍历时直接更新。这里直接看代码就好，和上面的解题方法，稍微有点不同

C++ 实现

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;

        if (root == nullptr) {
            return result;
        }

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            TreeNode* rightmostNode = nullptr;  // 记录当前层最右节点

            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();

                rightmostNode = node;  // 持续更新，最后一个就是最右节点，这样就不需要专门判断索引了

                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }

            // 将当前层的最右节点加入结果
            result.push_back(rightmostNode->val);
        }

        return result;
    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)