199.二叉树的右视图（BFS）

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

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

解题思路

本文使用Bfs思想，层序遍历，只保留最后一个结点的值。

/*** 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; // 存储每一层最后一个节点的值queue<TreeNode*> nodeQueue; // 队列用于BFSif (root == nullptr)return result;nodeQueue.push(root);      // 将根节点放入队列int currentLevelNodes = 1; // 当前层剩余要处理的节点数int nextLevelNodes = 0;    // 下一层的节点数while (!nodeQueue.empty()) {TreeNode* currentNode = nodeQueue.front();nodeQueue.pop();--currentLevelNodes; // 处理一个节点，当前层节点数减一if (currentNode->left != nullptr) {nodeQueue.push(currentNode->left);++nextLevelNodes; // 下一层节点数加一}if (currentNode->right != nullptr) {nodeQueue.push(currentNode->right);++nextLevelNodes; // 下一层节点数加一}// 如果当前层的节点已经全部处理完，则把当前节点的值添加到结果中，// 并重置当前层节点数为下一层的节点数if (currentLevelNodes == 0) {result.push_back(currentNode->val);currentLevelNodes = nextLevelNodes;nextLevelNodes = 0;}}return result;}
};