// Binary Tree Right Side View

// 时间复杂度O(n)，空间复杂度O(n)

public class Solution {

public List<Integer> rightSideView(TreeNode root) {

List<Integer> result = new ArrayList<>();

Queue<TreeNode> current = new LinkedList<>();

Queue<TreeNode> next = new LinkedList<>();

if(root == null) {

return result;

} else {

current.offer(root);

}

while (!current.isEmpty()) {

ArrayList<Integer> level = new ArrayList<>(); // elments in one level

while (!current.isEmpty()) {

TreeNode node = current.poll();

level.add(node.val);

if (node.left != null) next.add(node.left);

if (node.right != null) next.add(node.right);

}

result.add(level.get(level.size()-1));

// swap

Queue<TreeNode> tmp = current;

current = next;

next = tmp;

}

return result;

}

}