力扣199二叉树的右视图

发表于 更新于 分类于 Changyan：

199. 二叉树的右视图

问题

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

示例:

1
2
3
4
5
6
7
8
9
10

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

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/binary-tree-right-side-view

解答

参考甜姐的解答

二、DFS
我们按照 「根结点 -> 右子树 -> 左子树」 的顺序访问， 就可以保证每层都是最先访问最右边的节点的。
（与先序遍历 「根结点 -> 左子树 -> 右子树」 正好相反，先序遍历每层最先访问的是最左边的节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return res;
    }

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