LeetCode-199-二叉树的右视图

题目描述

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

思路

1、层序遍历，把每一层最后一个点添加进结果里

2、深度遍历，优先遍历右子树，当前的deep与结果的size比较

代码

/**
     * 层序遍历法
     * @param root 根节点
     * @return 右侧视图
     */
    public List<Integer> rightSideViewBFS(TreeNode199 root) {
        if (root == null) {
            return new ArrayList<Integer>();
        }

        ArrayList<Integer> res = new ArrayList<>();
        Queue<TreeNode199> queue = new LinkedList<>();

        queue.offer(root);
        while (!queue.isEmpty()) {
            //记录当前层的节点个数
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode199 node = queue.poll();

                if (node.left != null){
                    queue.offer(node.left);
                }

                if (node.right != null){
                    queue.offer(node.right);
                }

                //(i == size -1)为当前层最后一个点
                if (i == size -1){
                    res.add(node.val);
                }
            }
        }

        return res;
    }

/**
     * 深度优先遍历，右侧优先
     * @param root 根节点
     * @return 侧视图
     */
    public List<Integer> rightSideViewDFS(TreeNode199 root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        TreeNode199 ptr = root;
        res.add(ptr.val);

        DFS(ptr.right,2,res);
        DFS(ptr.left,2,res);

        return  res;
    }

	private void DFS(TreeNode199 root,int deep,List<Integer> res){
        if (root != null){
            if (deep > res.size()){
                res.add(root.val);
            }
            DFS(root.right,deep+1,res);
            DFS(root.left,deep+1,res);
        }
    }

LeetCode-199-二叉树的右视图

原文：https://www.cnblogs.com/rrryan/p/15194054.html