给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

思路:

层序遍历  找到最右边的

//层序遍历  找到最右边
	public List<Integer> rightSideView(TreeNode root) {
		List<Integer> res=new ArrayList<>();
		if (root==null) return res;
		Queue<TreeNode> queue=new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int size=queue.size();
			for (int i = 0; i < size; i++) {
			   TreeNode cur=queue.poll();
			   if (i==size-1)  res.add(cur.val); //把最右边的加进去
			   if (cur.left!=null) 
				   queue.add(cur.left);
			   if (cur.right!=null) 
				   queue.add(cur.right);
			}
		}
		return res;       
   }

2.dfs解法

//dfs解法
public List<Integer> rightSideView2(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        process(root, result, 0);
        return result;
    }
    
    public void process(TreeNode cur, List<Integer> result, int curDepth){
        if(cur == null){
            return;
        }
        if(curDepth == result.size()){
            result.add(cur.val);                    //每一层加进去的条件
        }
        
        process(cur.right, result, curDepth + 1); //先看右边
        process(cur.left, result, curDepth + 1);
        
    }