Description
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.
Examples:
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Example 2:
Input: root = [1,null,3]
Output: [1,3]
Example 3:
Input: root = []
Output: []Solution in Python
To solve the problem of returning the right side view of a binary tree, we can perform a level-order traversal (similar to a breadth-first search) but only keep track of the last node at each level, which is the node visible from the right side.
Steps
- Check for an Empty Tree: If the tree is empty (i.e., the root is
None), return an empty list. - Use a Queue for Level-Order Traversal: Utilize a queue to perform the level-order traversal. This will help us process nodes level by level.
- Track the Rightmost Node: For each level, track the last node we encounter, as it is the node visible from the right side.
- Store the Rightmost Nodes: Store the values of these rightmost nodes in a list.
- Return the List: Once all levels are processed, return the list of rightmost nodes.
Python
from typing import List, Optional
# 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]:
# If the tree is empty, return an empty list
if not root:
return []
# List to store the right side view
right_view = []
# Queue for level-order traversal
queue = [root]
# Perform level-order traversal
while queue:
# Number of nodes at the current level
level_length = len(queue)
# Iterate over all nodes at this level
for i in range(level_length):
# Get the current node
node = queue.pop(0)
# If this is the last node in the level, add its value to the right_view list
if i == level_length - 1:
right_view.append(node.val)
# Add left and right children to the queue if they exist
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Return the collected right side view
return right_viewExplanation
- Initialization:
- The function begins by checking if the
rootisNone. If it is, it returns an empty list because there is no tree to view from the right side.
- The function begins by checking if the
- Queue Setup:
- The
queueis initialized with the root node. This queue will help us traverse the tree level by level.
- The
- Level-Order Traversal:
- We enter a
whileloop that continues until thequeueis empty. - For each level, we calculate the number of nodes (
level_length) in that level, which allows us to determine which node is the last in the level.
- We enter a
- Processing Nodes:
- We then loop through each node in the current level. The last node processed in this loop (i.e., when
i == level_length - 1) is the rightmost node at that level and is added to theright_viewlist.
- We then loop through each node in the current level. The last node processed in this loop (i.e., when
- Children Nodes:
- For each node, if it has left or right children, they are added to the
queueto be processed in the next level.
- For each node, if it has left or right children, they are added to the
- Return the Result:
- After the loop completes,
right_viewcontains the values of the nodes visible from the right side, ordered from top to bottom, and is returned as the result.
- After the loop completes,
Solution in Javascript
JavaScript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function(root) {
// If the tree is empty, return an empty array
if (root === null) {
return [];
}
// Array to store the right side view
const rightView = [];
// Queue for level-order traversal
const queue = [root];
// Perform level-order traversal
while (queue.length > 0) {
// Number of nodes at the current level
const levelLength = queue.length;
// Iterate over all nodes at this level
for (let i = 0; i < levelLength; i++) {
// Get the current node from the front of the queue
const node = queue.shift();
// If this is the last node in the level, add its value to rightView
if (i === levelLength - 1) {
rightView.push(node.val);
}
// Add the left child to the queue if it exists
if (node.left !== null) {
queue.push(node.left);
}
// Add the right child to the queue if it exists
if (node.right !== null) {
queue.push(node.right);
}
}
}
// Return the collected right side view
return rightView;
};Solution in Java
Java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class Solution {
public List<Integer> rightSideView(TreeNode root) {
// List to store the right side view
List<Integer> rightView = new ArrayList<>();
// If the tree is empty, return an empty list
if (root == null) {
return rightView;
}
// Queue for level-order traversal
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
// Perform level-order traversal
while (!queue.isEmpty()) {
// Number of nodes at the current level
int levelSize = queue.size();
// Iterate over all nodes at this level
for (int i = 0; i < levelSize; i++) {
// Get the current node from the front of the queue
TreeNode currentNode = queue.poll();
// If this is the last node in the level, add its value to rightView
if (i == levelSize - 1) {
rightView.add(currentNode.val);
}
// Add the left child to the queue if it exists
if (currentNode.left != null) {
queue.add(currentNode.left);
}
// Add the right child to the queue if it exists
if (currentNode.right != null) {
queue.add(currentNode.right);
}
}
}
// Return the collected right side view
return rightView;
}
}Solution in C#
C#
using System.Collections.Generic;
public class Solution {
public IList<int> RightSideView(TreeNode root) {
// List to store the right side view
IList<int> rightView = new List<int>();
// If the tree is empty, return an empty list
if (root == null) {
return rightView;
}
// Queue for level-order traversal
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
// Perform level-order traversal
while (queue.Count > 0) {
// Number of nodes at the current level
int levelSize = queue.Count;
// Iterate over all nodes at this level
for (int i = 0; i < levelSize; i++) {
// Get the current node from the front of the queue
TreeNode currentNode = queue.Dequeue();
// If this is the last node in the level, add its value to rightView
if (i == levelSize - 1) {
rightView.Add(currentNode.val);
}
// Add the left child to the queue if it exists
if (currentNode.left != null) {
queue.Enqueue(currentNode.left);
}
// Add the right child to the queue if it exists
if (currentNode.right != null) {
queue.Enqueue(currentNode.right);
}
}
}
// Return the collected right side view
return rightView;
}
}