二叉树的右视图 🌟🌟🌟中等
课后作业
问题描述
原文链接：199. 二叉树的右视图
给定一个二叉树的根节点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
代码实现
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> res = new ArrayList<>();
queue.add(root);
while(!queue.isEmpty()){
// 每次进入循环时，队列的大小刚好是这一层的节点个数
int size = queue.size();
List<Integer> t = new ArrayList<>();
for(int i = 0; i < size; i++){
TreeNode temp = queue.poll();
t.add(temp.val);
if(temp.left != null){
queue.add(temp.left);
}
if(temp.right != null){
queue.add(temp.right);
}
}
res.add(t.get(t.size() - 1));
}
return res;
}
}
Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
queue = [root]
res = []
while queue:
size = len(queue)
t = []
for i in range(size):
temp = queue.pop(0)
t.append(temp.val)
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
res.append(t[-1])
return res
C++
/**
* 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) {
if (!root){
return {};
}
queue<TreeNode*> q;
vector<int> res;
q.push(root);
while(!q.empty()){
int size = q.size();
vector<int> t;
for (int i = 0; i < size; i++){
TreeNode* temp = q.front();
q.pop();
t.push_back(temp->val);
if (temp->left){
q.push(temp->left);
}
if (temp->right){
q.push(temp->right);
}
}
res.push_back(t[t.size()-1]);
}
return res;
}
};
Go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView(root *TreeNode) []int {
if root == nil {
return []int{}
}
queue := []*TreeNode{root}
res := []int{}
for len(queue) > 0 {
size := len(queue)
t := []int{}
for i := 0; i < size; i++ {
temp := queue[0]
queue = queue[1:]
t = append(t, temp.Val)
if temp.Left != nil {
queue = append(queue, temp.Left)
}
if temp.Right != nil {
queue = append(queue, temp.Right)
}
}
res = append(res, t[len(t)-1])
}
return res
}