BiruLyu
5/30/2017 - 6:11 PM

## 199. Binary Tree Right Side View(BFS).java

``````/**
* 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) {
List<Integer> result = new ArrayList<>();
calc(root, result,0);
return result;
}
public void calc(TreeNode root, List<Integer> result, int depth){
if(root==null) return;
if(depth==result.size()){ result.add(root.val); } //result depth basically shows for every depth level, there should be one node entered i.e. when result size is 2 there should be 2 elements when it's 3 there should be 3 n so on
calc(root.right, result, depth+1);
calc(root.left, result, depth+1);
}
}``````
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
/*
1. BFS时，先遍历右子树、后左子树，把每层的第一个加到res里，（如果res.size < level时，add，或者跳过）
2. BFS时，先左子树后右子树，每一层对应一个值，前面的会把后面的不断覆盖。
*/
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()) {
TreeNode cur = queue.peek();
int curSize = queue.size();
for(int i = 0; i < curSize; i++) {
cur = queue.poll();
if(cur.left != null) {
queue.offer(cur.left);
}
if(cur.right != null) {
queue.offer(cur.right);
}
}