二叉树的右视图

描述

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-right-side-view
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这道题要求我们打印出二叉树每一行最右边的一个数字，实际上是求二叉树层序遍历的一种变形，我们只需要保存每一层最右边的数字即可，还需要用到数据结构队列queue，遍历每层的节点时，把下一层的节点都存入到queue中，每当开始新一层节点的遍历之前，先把新一层最后一个节点值存到结果中，

C++代码

版本1：

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

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> rightSideView(TreeNode* root) {
    vector<int> res;
    if (!root) return res;  // 如果根节点为空，返回空的结果数组
    queue<TreeNode*> q;  // 定义一个队列，用于层序遍历
    q.push(root);  // 将根节点入队
    while (!q.empty()) {  // 当队列非空时
        int n = q.size();  // 当前层的节点个数
        for (int i = 0; i < n; i++) {  // 依次遍历当前层的所有节点
            TreeNode* node = q.front();  // 取出队首节点
            q.pop();  // 将队首节点出队
            if (i == n - 1) res.push_back(node->val);  // 如果是当前层的最后一个节点，将其值加入结果数组
            if (node->left) q.push(node->left);  // 如果左子节点不为空，将其入队
            if (node->right) q.push(node->right);  // 如果右子节点不为空，将其入队
        }
    }
    return res;
}

int main() {
    // 创建如下二叉树：
    //      1
    //    /   \
    //   2     3
    //    \     \
    //     5     4
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(4);
    vector<int> res = rightSideView(root);  // 获取二叉树的右视图
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";  // 输出结果
    }
    return 0;
}

版本2：

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        vector<vector<int>> temp;
        helper(temp, 0, root);
        for(int i=0; i<temp.size(); i++){
            res.push_back(temp[i].back());
        }
        return res;
    }

    void helper(vector<vector<int>>& temp, int level, TreeNode* root){
        if(!root) return;
        if(level == temp.size()) temp.push_back({});
        temp[level].push_back(root->val);
        helper(temp, level+1, root->left);
        helper(temp, level+1, root->right);
    }
};

Python代码

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rightSideView(root: TreeNode) -> List[int]:
    res = []
    if not root:
        return res  # 如果根节点为空，返回空的结果数组
    q = [root]  # 定义一个队列，用于层序遍历
    while q:  # 当队列非空时
        n = len(q)  # 当前层的节点个数
        for i in range(n):  # 依次遍历当前层的所有节点
            node = q.pop(0)  # 取出队首节点
            if i == n - 1:
                res.append(node.val)  # 如果是当前层的最后一个节点，将其值加入结果数组
            if node.left:
                q.append(node.left)  # 如果左子节点不为空，将其入队
            if node.right:
                q.append(node.right)  # 如果右子节点不为空，将其入队
    return res

# 创建如下二叉树：
#      1
#    /   \
#   2     3
#    \     \
#     5     4
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
root.right.right = TreeNode(4)

res = rightSideView(root)  # 获取二叉树的右视图
print(res)  # 输出结果：[1, 3, 4]