/**
* 199. 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 <—
*/
Here is the solution at github: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/BinaryTreeRightSideView.java
Observation: You can do a level order traversal via utilizing a queue. Per level order traversal you add the first child to output. For each level you add right item to queue before the left item so that if right item exists it will get processed first.
Here is the code:
public List<Integer> rightSideView(TreeNode root) {
if (root == null) return new ArrayList<> ();
List<Integer> out = new ArrayList<>();
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size(); //get the size of queue and only process that many items off of the queue
boolean toAdd = true;
for (int i =0; i < size; i++) {
TreeNode node = queue.poll();
if (toAdd) {
out.add(node.val);
toAdd = false;
}
if (node.right != null) {
queue.add(node.right);
}
if (node.left != null) {
queue.add(node.left);
}
}
}
return out;
}