Leetcode每日一题-二叉树的右视图

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

示例:

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

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

解题思路

树的遍历，题目要求返回树最又层的那一列，首先想到的是DFS和BFS，因为不知道每个分支的深度，所以在DFS深度遍历时，要记得当前深度有没有记录过最右边的节点，同理在BFS宽度遍历时，也要确保最右侧的节点被记录过。

DFS解法

class Solution {
    public List<Integer> rightSideView(TreeNode root) {

        List<Integer> list = new ArrayList<Integer>();
        int depth = 0;
        dfs(list,root,depth);
        return list;
    }

    private void dfs(List<Integer> list,TreeNode root,int depth)
    {
        if(root != null)
        {
            if(depth == list.size())
            {
                list.add(root.val);
            }
            depth++;
            dfs(list,root.right,depth);//优先访问右侧节点
            dfs(list,root.left,depth);
        }
    }
}

BFS解法

class Solution {
   
    public List<Integer> rightSideView(TreeNode root){
        List<Integer> list = new ArrayList<Integer>();

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if(root == null) return list;

        queue.offer(root);

        while(!queue.isEmpty())
        {
            //获取一层中最右边的那个节点
            int size = queue.size();  //提前算出来大小，因为大小时刻在变
            for(int i=0;i<size;i++)
            {
                TreeNode node = queue.poll();
                if(i == size -1)
                {
                    if(node != null) list.add(node.val);
                }
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }

        }

        return list;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。