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

public class Solution {

public List<Integer> rightSideView(TreeNode root) {

// use queue();

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

if (root == null) {

return list;

}

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

q.offer(root);

while (!q.isEmpty()) {

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

TreeNode tmp = null;

while(!q.isEmpty()) {

tmp = q.poll();

if (tmp.left != null) {

sameLevel.offer(tmp.left);

}

if (tmp.right != null) {

sameLevel.offer(tmp.right);

}

}

q = sameLevel;

list.add(tmp.val);

}

return list;

}

}

other's solution:

public List<Integer> rightSideView(TreeNode root) {

if(root==null)

return new ArrayList<Integer>();

List<Integer> left = rightSideView(root.left);

List<Integer> right = rightSideView(root.right);

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

re.add(root.val);

for(int i=0;i<Math.max(left.size(), right.size());i++){

if(i>=right.size())

re.add(left.get(i));

else

re.add(right.get(i));

}

return re;

}