这个题目其实没啥说的，就是层次遍历，每次都取那一层的最后一个就行。只是编码过程中有一些边界条件需要注意，再有就是这种需要保存上一层状态的题目，一般是需要两个队列的，来轮流保存每层的节点，代码如下：
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();if (root == null)return result;if (root.left == null && root.right == null) {
result.add(root.val);return result;}Queue<TreeNode> queue1 = new LinkedList<>();Queue<TreeNode> queue2 = new LinkedList<>();//先将根节点加入到队列中queue1.add(root);while (!queue1.isEmpty() || !queue2.isEmpty()) {
TreeNode finalCur = null; //记录一层最后的节点while (!queue1.isEmpty()) {
TreeNode curNode = queue1.remove();if (curNode.left != null)queue2.add(curNode.left);if (curNode.right != null)queue2.add(curNode.right);finalCur = curNode;}//如果finalCur不为空说明queue1保存的那层遍历了，所以要取出那一层最后一个if (finalCur != null)result.add(finalCur.val);//重置，让它在queue2中继续寻找最后一个finalCur = null;while (!queue2.isEmpty()) {
TreeNode curNode = queue2.remove();if (curNode.left != null)queue1.add(curNode.left);if (curNode.right != null)queue1.add(curNode.right);finalCur = curNode;}//不为空说明queue2保存的那层也遍历了，取出那一层最后一个if (finalCur != null)result.add(finalCur.val);}return result;}
2020.2.8
更新来了，我写的代码真傻，原来真的是自己看自己原来写的代码怎么看怎么恶心。
一、广度优先遍历
还是上面那个思路，但是简单多了
public List<Integer> rightSideView(TreeNode root) {
if (root == null) {
return new ArrayList<>();}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);List<Integer> ret = new ArrayList<>();while (!queue.isEmpty()) {
int size = queue.size(); //记录下当前这一层的节点数for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();if (i == size - 1) {
//到最后一个结点时就可以加到结果中，而不需要两个队列轮流存储ret.add(node.val);}if (node.left != null) {
//把弹出队列的左子树和右子树都加到队列中queue.add(node.left);}if (node.right !=null) {
queue.add(node.right);}}}return ret;}
二、深度优先遍历
深度优先遍历其实也不难，因为我们肯定是访问的最右边的那一层，所以我们参考先序递归遍历的思路
- 先访问根节点，然后它是右视图的一个结点
- 然后访问右子树
- 紧接着访问左子树
但是要注意的是，这个过程中我们在判断一个结点是不是右视图的时候，要增加一个参数level，代表我们当前访问到了第几层，如果result中的元素数目和当前层数相同，说明当前层中已经有一个右视图结点了，所以我们就不要添加了。而我们怎么保证这个右视图一定是我们想要的右视图呢，是因为我们遍历的顺序是先遍历右子树。
先访问结点的右子树，然后再访问结点
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();helper(root, result, 1);return result;}private void helper(TreeNode root, List<Integer> result, int curLevel) {
if (root == null)return;if (result.size() < curLevel) //只有当前层的结点还未加入到result时，才把它加进去result.add(root.val);helper(root.right, result, curLevel+1); //递归遍历右子树，level要+1helper(root.left, result, curLevel+1); //递归遍历左子树，level要+1}
}