### 题目

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].

### DFS. 先右后左的inorder遍历。递归版。

    1       // 顺序：1-3-2
/ \
2   3


#### 代码

public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList<>();
recursion(root,1,new int[]{0},ret);
return ret;
}
public void recursion(TreeNode root, int depth, int[] maxDepth, List<Integer> ret) {
if (root == null) { return; }
if (depth > maxDepth[0]) {
maxDepth[0] = depth;
}
recursion(root.right, depth+1,maxDepth,ret);
recursion(root.left, depth+1,maxDepth,ret);
}
}


public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList<>();
recursion(root,1,ret);
return ret;
}
public void recursion(TreeNode root, int depth, List<Integer> ret) {
if (root == null) { return; }
if (depth > ret.size()) { ret.add(root.val); }
recursion(root.right,depth+1,ret);
recursion(root.left,depth+1,ret);
}
}


### DFS. 先右后左的inorder遍历。迭代版。

#### 代码

public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList<>();
int depth = 0, maxDepth = 0;
TreeNode cur = root;
while (cur != null || !nodeStack.isEmpty()) {
while (cur != null) {
nodeStack.offerFirst(cur);
depthStack.offerFirst(++depth);
if (depth > maxDepth) {
maxDepth = depth;
}
cur = cur.right;
}
cur = nodeStack.pollFirst().left;
depth = depthStack.pollFirst();
}
return ret;
}
}


### BFS. 记录每层第一个元素

#### 代码

public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList<>();
while (!level.isEmpty()) {
int size = level.size();
boolean findFirst = false;
for (int i = 0; i < size; i++) {
TreeNode node = level.remove(0);
if (node != null) {
if (!findFirst) { ret.add(node.val); findFirst = true; }