二连水
题目地址：
https://leetcode.com/problems/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.
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.
题目解析：
乍一看，酷炫异常，实际上单纯得让人想哭。
让你找到二叉树每层的最后一个元素。
怎么早？
BFS一层，队列的最后一个节点。
具体代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
Deque<TreeNode> bfs = new LinkedList<TreeNode>();
List<Integer> result = new ArrayList<Integer>();
if (root == null) {
return result;
}
bfs.add(root);
while (!bfs.isEmpty()) {
TreeNode last = bfs.getLast();
result.add(last.val);
TreeNode first = bfs.getFirst();
while (first != last) {
if (first.left != null) {
bfs.add(first.left);
}
if (first.right != null) {
bfs.add(first.right);
}
bfs.pop();
first = bfs.getFirst();
}
// handle last
if (last.left != null) {
bfs.add(last.left);
}
if (last.right != null) {
bfs.add(last.right);
}
bfs.pop();
}
return result;
}
}