二叉树的右视图（ LeetCode 199 ）
一、题目描述
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的右视图（ LeetCode 199 ）: https://leetcode-cn.com/problems/binary-tree-right-side-view/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
// 设置一个数组用来存储二叉树的右视图结果
// 题目要求存储的是节点的值，所以类型是 Integer
List<Integer> list = new LinkedList<>();
// 设置一个队列，用来保存二叉树每一层的节点
Queue<TreeNode> que = new LinkedList<>();
// 边界判断
if (root == null) return list;
// 首先，把二叉树的根节点加入到队列中
que.add(root);
// 观察队列是否为空
while (!que.isEmpty()) {
// 1、获取队列的长度
int levelSize = que.size();
// 2、通过一个循环，获取队列中每个节点的左右子树，把这些左右子树节点也添加到队列中
for (int i = 0; i < levelSize; i++) {
// 3、弹出队列的队首元素
TreeNode node = que.poll();
// 4、判断弹出的节点是否有左子树
if (node.left != null) {
// 如果有左子树，把它加入到队列中
que.add(node.left);
}
// 5、判断弹出的节点是否有右子树
if (node.right != null) {
// 如果有右子树，把它加入到队列中
que.add(node.right);
}
// 对于每一层的二叉树节点，我们是从左到右依次添加，所以末尾的节点的顺序是 levelSize - 1
// 6、这个末尾的节点就是这一层中最右侧的节点
if (i == levelSize - 1) {
// 把最右侧的节点值加入到结果中
list.add(node.val);
}
}
}
// 返回结果
return list;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的右视图（ LeetCode 199 ）: https://leetcode-cn.com/problems/binary-tree-right-side-view/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
// 设置一个数组用来存储二叉树的右视图结果
// 题目要求存储的是节点的值，所以类型是 Integer
vector<int> list;
// 设置一个队列，用来保存二叉树每一层的节点
queue<TreeNode*> que;
// 边界判断
if (root == NULL) return list;
// 首先，把二叉树的根节点加入到队列中
que.push(root);
// 观察队列是否为空
while (!que.empty()) {
// 1、获取队列的长度
int levelSize = que.size();
// 2、通过一个循环，获取队列中每个节点的左右子树，把这些左右子树节点也添加到队列中
for (int i = 0; i < levelSize; i++) {
// 3、弹出队列的队首元素
TreeNode* node = que.front();
que.pop();
// 4、判断弹出的节点是否有左子树
if (node->left != NULL) {
// 如果有左子树，把它加入到队列中
que.push(node->left);
}
// 5、判断弹出的节点是否有右子树
if (node->right != NULL) {
// 如果有右子树，把它加入到队列中
que.push(node->right);
}
// 对于每一层的二叉树节点，我们是从左到右依次添加，所以末尾的节点的顺序是 levelSize - 1
// 6、这个末尾的节点就是这一层中最右侧的节点
if (i == levelSize - 1) {
// 把最右侧的节点值加入到结果中
list.push_back(node->val);
}
}
}
// 返回结果
return list;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树的右视图（ LeetCode 199 ）: https://leetcode-cn.com/problems/binary-tree-right-side-view/
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
# 设置一个数组用来存储二叉树的右视图结果
# 题目要求存储的是节点的值，所以类型是 Integer
list = []
# 设置一个队列，用来保存二叉树每一层的节点
que = deque()
# 边界判断
if not root :
return list
# 首先，把二叉树的根节点加入到队列中
que.append(root)
# 观察队列是否为空
while que:
# 1、获取队列的长度
levelSize = len(que)
# 2、通过一个循环，获取队列中每个节点的左右子树，把这些左右子树节点也添加到队列中
for i in range(levelSize):
# 3、弹出队列的队首元素
node = que.popleft()
# 4、判断弹出的节点是否有左子树
if node.left :
# 如果有左子树，把它加入到队列中
que.append(node.left)
# 5、判断弹出的节点是否有右子树
if node.right :
# 如果有右子树，把它加入到队列中
que.append(node.right)
# 对于每一层的二叉树节点，我们是从左到右依次添加，所以末尾的节点的顺序是 levelSize - 1
# 6、这个末尾的节点就是这一层中最右侧的节点
if i == levelSize - 1 :
# 把最右侧的节点值加入到结果中
list.append(node.val)
# 返回结果
return list
