Sponsored
Sponsored
The Breadth-First Search (BFS) approach involves traversing the tree level by level using a queue. For each level, we capture the last node's value visible when viewed from the right side. This can be done by iterating through each level and storing the value of the last node encountered. This approach ensures that the elements are captured in top-to-bottom order as required.
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(w), where w is the maximum width of the tree (at the level with the most nodes).
1import java.util.ArrayList;
2import java.util.LinkedList;
3import java.util.List;
4import java.util.Queue;
5
6class TreeNode {
7 int val;
8 TreeNode left;
9 TreeNode right;
10 TreeNode() {}
11 TreeNode(int val) { this.val = val; }
12 TreeNode(int val, TreeNode left, TreeNode right) {
13 this.val = val;
14 this.left = left;
15 this.right = right;
16 }
17}
18
19public class Solution {
20 public List<Integer> rightSideView(TreeNode root) {
21 List<Integer> view = new ArrayList<>();
22 if (root == null) return view;
23
24 Queue<TreeNode> queue = new LinkedList<>();
25 queue.add(root);
26
27 while (!queue.isEmpty()) {
28 int levelSize = queue.size();
29 Integer lastNode = null;
30 for (int i = 0; i < levelSize; i++) {
31 TreeNode node = queue.poll();
32 lastNode = node.val;
33 if (node.left != null) {
34 queue.add(node.left);
35 }
36 if (node.right != null) {
37 queue.add(node.right);
38 }
39 }
40 view.add(lastNode);
41 }
42
43 return view;
44 }
45}We use a queue to traverse each level of the tree. For each level, we store the last node encountered, as this will be the rightmost node visible from that level. This approach guarantees capturing the right side view, storing the rightmost visible node at each tree level.
In this approach, a recursive Depth-First Search (DFS) is utilized. It traverses the tree from the root and prioritizes the right child before the left child at each node. By keeping track of the current level, we ensure to capture only the first node visited at that level, which represents the right view at that height.
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(h), where h is the height of the tree, considering the space used for recursion stack.
1using System.Collections.Generic;
2
3public class TreeNode {
4 public int val;
5 public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public IList<int> RightSideView(TreeNode root) {
var view = new List<int>();
DFS(root, 0, view);
return view;
}
private void DFS(TreeNode node, int level, List<int> view) {
if (node == null) return;
if (level == view.Count) {
view.Add(node.val);
}
DFS(node.right, level + 1, view);
DFS(node.left, level + 1, view);
}
}The DFS strategy involves recursion, starting with the right child node at each step. This ensures capturing the rightmost nodes of the tree from top to bottom. Nodes are added to the list if they are the first nodes encountered at their respective levels.