199. 二叉树的右视图

199. 二叉树的右视图

难度中等 416

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

示例:

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

输出: [1, 3, 4]

解释:

1            <—

/   \

2     3         <—

\     \

5     4       <—

public List<Integer> rightSideView(TreeNode root) &#123;
        Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
        int max_depth = -1;

        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<Integer> depthQueue = new LinkedList<Integer>();
        nodeQueue.add(root);
        depthQueue.add(0);

        while (!nodeQueue.isEmpty()) &#123;
            TreeNode node = nodeQueue.remove();//等价removeFirst
            int     depth = depthQueue.remove();

            if (node != null) &#123;
                // 维护二叉树的最大深度
                max_depth = Math.max(max_depth, depth);

                // 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
                rightmostValueAtDepth.put(depth, node.val);

                nodeQueue.add(node.left);
                nodeQueue.add(node.right);
                depthQueue.add(depth + 1);
                depthQueue.add(depth + 1);
            &#125;
        &#125;

        List<Integer> rightView = new ArrayList<Integer>();
        for (int depth = 0; depth <= max_depth; depth++) &#123;// =
            rightView.add(rightmostValueAtDepth.get(depth));
        &#125;

        return rightView;
    &#125;

---

BFS

public List<Integer> rightSideView(TreeNode root) &#123;
        List<Integer> res = new ArrayList<>();
        if (root == null) &#123;
            return res;
        &#125;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) &#123;
            int size = queue.size();
            for (int i = 0; i < size; i++) &#123;
                TreeNode node = queue.poll();
                if (node.left != null) &#123;
                    queue.offer(node.left);
                &#125;
                if (node.right != null) &#123;
                    queue.offer(node.right);
                &#125;
                if (i == size - 1) &#123;  //将当前层的最后一个节点放入结果列表
                    res.add(node.val);
                &#125;
            &#125;
        &#125;
        return res;
    &#125;

作者：sweetiee
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/solution/jian-dan-bfsdfs-bi-xu-miao-dong-by-sweetiee

####

---

DFS

    List<Integer> res = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) &#123;
        dfs(root, 0); // 从根节点开始访问，根节点深度是0
        return res;
    &#125;

    private void dfs(TreeNode root, int depth) &#123;
        if (root == null) &#123;
            return;
        &#125;
        // 先访问 当前节点，再递归地访问 右子树 和 左子树。
        if (depth == res.size()) &#123; // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
            res.add(root.val);
        &#125;
        depth++;
        dfs(root.right, depth);///先添加又节点,执行左节点时 不满足if depth== 条件。
        dfs(root.left, depth);
    &#125;

作者：sweetiee
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/solution/jian-dan-bfsdfs-bi-xu-miao-dong-by-sweetiee/