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

这道题想到了dfs的解法，跟之前做的一道题类似。然而突然发现可以用bfs做，每一层取最右边的那一个元素就可以。待会看看给补上。

dfs的解法比较巧妙，这里按照层去往result结果集添加结果，采用先序遍历，因为根节点这一层没有个跟它同一层的点，所以可以先计算也可以后计算。因为看的是右试图，所以需要先递归左孩子然后递归右孩子，这样如果右孩子有跟左孩子同一层的元素可以更新；这样子，填写result list的顺序就是顺序的，所以也就是可以直接返回的顺序。

代码：

public List<Integer> rightSideView(TreeNode root) { List<Integer> result = new ArrayList<>(); if(root == null) return result; dfs(result, root, 0); return result; } private void dfs(List<Integer> result, TreeNode root, int level){ if(root == null) return; if(result.size() == level){ result.add(root.val); }else{ result.set(level, root.val); } dfs(result, root.left, level+1); dfs(result, root.right, level+1); }

使用bfs来写也是可以的，不过不知道为什么效率会差很多。但是思路很清楚，用两个技术统计当前层的个数和上一层的个数，当上一层的个数减小到0的时候，说明上面那一层刚好走到最后一个元素，这个时候把最后一个元素添加到结果集当中（顺序添加就好）。然后当前层的个数赋值给前一层，当前层的个数重置为0.

也就是一般的bfs。

代码：

public List<Integer> rightSideView(TreeNode root) { List<Integer> result = new ArrayList<>(); if(root == null) return result; bfs(result, root); return result; } private void bfs(List<Integer> result, TreeNode root){ Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int preLevel = 1; int curLevel = 0; int level = 0; while(!queue.isEmpty()){ TreeNode node = queue.poll(); if(node.left != null){ curLevel++; queue.offer(node.left); } if(node.right != null){ curLevel++; queue.offer(node.right); } preLevel--; if(preLevel == 0){ System.out.println("add:"+node.val); result.add(level++, node.val); preLevel = curLevel; curLevel = 0; } } }