Intuition
We aim to find the right side view of a binary tree, which is the last visible node at each level when viewed from the right.
Approach
I initially attempted a different approach, but it turned out to be more complex and time-consuming. 😅 However, I soon discovered that using a queue-based level-order traversal made the solution much more manageable. 🚀 This approach allowed me to easily find the rightmost node at each level and add its value to the result list. It was like the binary tree itself was guiding me towards the simpler path!
Complexity
- Time complexity: O(n) where n is the number of nodes in the tree.
- Space complexity: O(n) in the worst case when the binary tree is completely unbalanced.
Code
/**
* 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> result = new ArrayList<>();
if(root == null){
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0 ; i < size ; i++)
{
TreeNode node = queue.poll();
if(i == size - 1){
result.add(node.val);
}
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
}
return result;
}
}
Happy coding,
shiva
Top comments (0)