Binary Tree Right Side View | Leetcode

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.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

---

Solution: Maintain a list of integers "answer" such that the value at index i is the last node we we saw at height i. Traverse the tree in breadth-first search (BFS) order, keeping the height info of each node. For each node, set the value in "answer" at index "height" with the node's value. When you are done traversing, you will get the answer in "answer".

I can think of two other ways to solve the problem:

1. Maintain two queues, one for the current level and another for the next level. Traverse BFS by using the current level queue and add all children nodes to the next level queue. At the end of each level, add the last seen node's value to the answer.
2. Traverse BFS as per the algoritm shown below. Whenever the height changes, add the last seen node's value to the answer. After the traversal, if we have any level not added to the answer yet, add it.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private static class TreeNodeWithHeight {
        private TreeNode treeNode;
        private int height;
        
        private TreeNodeWithHeight(TreeNode treeNode, int height) {
            this.treeNode = treeNode;
            this.height = height;
        }
    }
    
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) return Collections.emptyList();
        
        List<Integer> answer = new ArrayList<>();
        LinkedList<TreeNodeWithHeight> bfsQueue = new LinkedList<>();
        bfsQueue.addLast(new TreeNodeWithHeight(root, 0));
        
        do {
            TreeNodeWithHeight nodeWithHeight = bfsQueue.removeFirst();
            TreeNode node = nodeWithHeight.treeNode;
            int height = nodeWithHeight.height;
            
            if (height == answer.size()) {
                answer.add(node.val);
            } else {
                answer.set(height, node.val);
            }
            
            if (node.left != null) {
                bfsQueue.addLast(new TreeNodeWithHeight(node.left, height + 1));
            }
            if (node.right != null) {
                bfsQueue.addLast(new TreeNodeWithHeight(node.right, height + 1));
            }
        } while (!bfsQueue.isEmpty());
        
        return answer;
    }
}