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].
这道题很简单。只要用BFS：一层一层地遍历，然后取每一层最右边的结点值 就好了。 public List<Integer> rightSideView(TreeNode root) { List<Integer> result=new ArrayList<Integer>(); if(root==null){ return result; } Queue<TreeNode> queue=new LinkedList<TreeNode>(); queue.offer(root); while(!queue.isEmpty()){ int size=queue.size(); for(int i=0;i<size;i++){ TreeNode node=queue.poll(); if(node.left!=null){ queue.offer(node.left); } if(node.right!=null){ queue.offer(node.right); } if(i==size-1){ result.add(node.val); } } } return result; }大神也有递归的解法。主要思想是： 1. 树的每一层只取一个结点 2. 因此当前 result list 的 size 就是深度。如果当前深度=list.size()，说明当前深度的结点还没加到list中，因此进行添加操作。如果当前深度<list.size(),说明当前深度的结点已经加到list中，继续向深处递归。
public class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); rightView(root, result, 0); return result; } public void rightView(TreeNode curr, List<Integer> result, int currDepth){ if(curr == null){ return; } if(currDepth == result.size()){ result.add(curr.val); } rightView(curr.right, result, currDepth + 1); rightView(curr.left, result, currDepth + 1); } }
