Problem
Binary Tree Right Side View
Given 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:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
1 <---
/ \
2 3 <---
\ \
5 4 <---
Solution
We can do level traversal the tree and add the last element of a level to the result. For level traversal, we can use a queue to store the elements in the next level, and use the size to remember how many elements to process for the next level.
import java.util.*;
class Solution {
public static void main(String[] args) {
Node root = new Node(1,
new Node(2, null, new Node(5, null, null)),
new Node(3, null, new Node(4, null, null)));
List<Integer> result = solve(root);
result.stream().forEach(System.out::println);
}
private static List<Integer> solve(Node root) {
List<Integer> result = new ArrayList<>();
if(root == null) return result;
Queue<Node> queue = new ArrayDeque<>();
queue.offer(root);
int size = queue.size();
while(!queue.isEmpty()) {
for(int i = 0; i < size; i++) {
Node cur = queue.poll();
if(cur.left != null)
queue.offer(cur.left);
if(cur.right != null)
queue.offer(cur.right);
if(i == size - 1)
result.add(cur.val);
}
size = queue.size();
}
return result;
}
static class Node {
int val;
Node left;
Node right;
public Node(int val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}
The time complexity is O(N) because we need to touch each node, and space complexity is O(N) because the queue in the worst can grow to N/2.
An alternative solution is to use recursive solution with a level marker. The right-most node will equal to the level marker then increase the level marker, so that the other nodes in the same level no longer equal to the level marker so won't be added to the final result.
import java.util.*;
class Solution {
private List<Integer> result = new ArrayList<>();
public static void main(String[] args) {
Node root = new Node(1,
new Node(2, null, new Node(5, null, null)),
new Node(3, null, new Node(4, null, null)));
Solution sol = new Solution();
int level = 0;
sol.dfs(root, level);
sol.result.stream().forEach(System.out::println);
}
private void dfs(Node root, int level) {
if(root == null)
return;
if(level == result.size()) {
result.add(root.val);
}
if(root.right != null) {
dfs(root.right, level + 1);
}
if(root.left != null) {
dfs(root.left, level + 1);
}
}
static class Node {
int val;
Node left;
Node right;
public Node(int val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}
The time complexity is O(N), the space complexity is O(H) which equal to the caller stack size.
