199. 二叉树的右视图(中等)

1，问题描述

199. 二叉树的右视图

难度：中等

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

示例 1：

**输入：**root = [1,2,3,null,5,null,4]

输出：[1,3,4]

解释：

示例 2：

**输入：**root = [1,2,3,4,null,null,null,5]

输出：[1,3,4,5]

解释：

示例 3：

**输入：**root = [1,null,3]

输出：[1,3]

示例 4：

**输入：**root = []

输出：[]

提示:

• 二叉树的节点个数的范围是 [0,100]
• -100 <= Node.val <= 100

2，初步思考

​ 依据先验知识，我想到了层序遍历，选取每层最后一个元素

​ 在看了官方题解后，发现其实我这个层序遍历的是bfs广度优先搜索算法，然后还有一个深度优先搜索算法

3，代码处理

import support.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class _199二叉树的右视图 {
    // 解法：广度优先搜索 bfs
    // 直接层序遍历，取最后一个元素即可
    public List<Integer> rightSideView_bfs(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        List<TreeNode> temp = new ArrayList<>();
        if (root == null) {
            return res;
        }
        temp.add(root);
        while (!temp.isEmpty()) {
            res.add(temp.get(temp.size() - 1).val);
            List<TreeNode> tempCur = new ArrayList<>();
            for (TreeNode treeNode : temp) {
                if (treeNode != null) {
                    if (treeNode.left != null) tempCur.add(treeNode.left);
                    if (treeNode.right != null) tempCur.add(treeNode.right);
                }
            }
            temp = tempCur;
        }
        return res;
    }

    // 解法：深度优先搜索 dfs
    public List<Integer> rightSideView_dfs(TreeNode root) {
        dfs(root, 0);
        return res;
    }

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

    private void dfs(TreeNode root, int depth) {
        if (root == null) return;
        if (res.size() == depth) {
            res.add(root.val);
        }
        dfs(root.right, depth + 1);
        dfs(root.left, depth + 1);
    }
}