题目描述

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

题目分析

迭代

使用队列，层序遍历，记录每层的数量，在每层对后一个数字出队时，记录下来

递归

按照 中 -> 右 -> 左 的顺序进行递归遍历，维护当前的深度，当深度大于结果的大小时，说明是第一次来到这个层级，且是最右侧先遍历，所以把当前值加入结果中

Java

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    dfs(root, ans, 1);
    return ans;
}

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

Kotlin

fun rightSideView(root: TreeNode?): List<Int> {
    val queue = LinkedList<TreeNode>()
    val ans = ArrayList<Int>()
    if (root == null) {
        return ans
    }
    queue.offer(root)
    while (!queue.isEmpty()) {
        var size = queue.size
        while (size > 0) {
            val node = queue.poll()
            if (node.left != null) {
                queue.offer(node.left)
            }
            if (node.right != null) {
                queue.offer(node.right)
            }
            if (size == 1) {
                ans.add(node.`val`)
            }
            size--
        }
    }
    return ans
}