-
comments: true
-
difficulty: Medium
-
tags:
- Tree
- Depth-First Search
- Breadth-First Search
- Binary Tree
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation:
Example 2:
Input: root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Explanation:
Example 3:
Input: root = [1,null,3]
Output: [1,3]
Example 4:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
We can use breadth-first search (BFS) and define a queue
The time complexity is
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
ans = []
if root is None:
return ans
q = deque([root])
while q:
ans.append(q[0].val)
for _ in range(len(q)):
node = q.popleft()
if node.right:
q.append(node.right)
if node.left:
q.append(node.left)
return ans/**
* 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) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
ans.add(q.peekFirst().val);
for (int k = q.size(); k > 0; --k) {
TreeNode node = q.poll();
if (node.right != null) {
q.offer(node.right);
}
if (node.left != null) {
q.offer(node.left);
}
}
}
return ans;
}
}/**
* 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*> q{{root}};
while (q.size()) {
ans.push_back(q.front()->val);
for (int k = q.size(); k; --k) {
auto node = q.front();
q.pop();
if (node->right) {
q.push(node->right);
}
if (node->left) {
q.push(node->left);
}
}
}
return ans;
}
};/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView(root *TreeNode) (ans []int) {
if root == nil {
return
}
q := []*TreeNode{root}
for len(q) > 0 {
ans = append(ans, q[0].Val)
for k := len(q); k > 0; k-- {
node := q[0]
q = q[1:]
if node.Right != nil {
q = append(q, node.Right)
}
if node.Left != nil {
q = append(q, node.Left)
}
}
}
return
}/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function rightSideView(root: TreeNode | null): number[] {
const ans: number[] = [];
if (!root) {
return ans;
}
const q: TreeNode[] = [root];
while (q.length > 0) {
ans.push(q[0].val);
const nq: TreeNode[] = [];
for (const { left, right } of q) {
if (right) {
nq.push(right);
}
if (left) {
nq.push(left);
}
}
q.length = 0;
q.push(...nq);
}
return ans;
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell
<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None,
// }
// }
// }
use std::collections::VecDeque;
impl Solution {
pub fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut ans = Vec::new();
if root.is_none() {
return ans;
}
let mut queue = VecDeque::new();
queue.push_back(root);
while !queue.is_empty() {
let len = queue.len();
ans.push(queue.front().unwrap().borrow().val);
for _ in 0..len {
let node = queue.pop_front().unwrap();
if node.borrow().right.is_some() {
queue.push_back(node.borrow().right.clone());
}
if node.borrow().left.is_some() {
queue.push_back(node.borrow().left.clone());
}
}
}
ans
}
}To solve this problem, we can use a breadth-first search (BFS) approach. The idea is to traverse the tree level by level and collect the first node that is visible from the right side at each level. This can be achieved by using a queue to store the nodes of the tree and processing each level one by one. At each level, we add the first node to our result list since it represents the rightmost node at that level. This ensures that the nodes we collect are in the correct order.
- Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited exactly once during the BFS traversal.
- Space Complexity: O(n), where n is the maximum number of nodes at any level in the tree, which can be at most the number of leaf nodes in the tree.