📝 题目描述

题目链接：二叉树的右视图

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

示例：

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

💡 解题思路

方法一：深度优先搜索

我们对树进行深度优先搜索，在搜索过程中，我们总是先访问右子树。那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点。

这样一来，我们可以存储在每个深度访问的第一个结点，一旦我们知道了树的层数，就可以得到最终的结果数组。

上图表示了问题的一个实例。红色结点自上而下组成答案，边缘以访问顺序标号。

方法二：广度优先搜索

比较容易想到的方法，借助层序遍历，遍历每一层，保留其最右的节点即可。

🔧 代码实现

1、深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if (!root) return ans;

        // 用 pair 将节点和深度绑定
        stack<pair<TreeNode*, int>> st;
        st.push({root, 0});

        while (!st.empty()) {
            auto [node, depth] = st.top(); 
            st.pop();

            // 如果当前深度刚好等于 ans 的大小，说明是该层第一个访问的节点（即最右节点）
            if (depth == ans.size()) {
                ans.push_back(node->val);
            }

            // 注意栈是先进后出：我们要先访问右节点，所以必须先压入左节点！
            if (node->left) st.push({node->left, depth + 1});
            if (node->right) st.push({node->right, depth + 1});
        }

        return ans;
    }
};

2、广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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> ans;
        if (!root) return ans;
        queue<TreeNode*> qu;
        qu.push(root);
        while(!qu.empty()){
            int size = qu.size();
            for(int i = 0; i < size - 1; i++) {
                TreeNode* temp = qu.front(); qu.pop();
                if (temp -> left) qu.push(temp -> left);
                if (temp -> right) qu.push(temp -> right);
            }
            TreeNode* temp = qu.front(); qu.pop();
            ans.push_back(temp -> val);
            if (temp -> left) qu.push(temp -> left);
            if (temp -> right) qu.push(temp -> right);
        }
        return ans;
    }
};

📊 复杂度分析

1、深度优先搜索

  • 时间复杂度：O(n)O(n)，深度优先搜索最多访问每个结点一次，因此是线性复杂度。
  • 空间复杂度：O(n)O(n)，最坏情况下，栈内会包含接近树高度的结点数量，占用 O(n)O(n) 的空间。

2、广度优先搜索

  • 时间复杂度：O(n)O(n)，每个节点最多进队列一次，出队列一次，因此广度优先搜索的复杂度为线性。
  • 空间复杂度：O(n)O(n)，每个节点最多进队列一次，所以队列长度最大不不超过 n，所以这里的空间代价为 O(n)O(n)。

🎯 总结

  • 核心思想：将右视图转化为熟悉的遍历方法。