199.二叉树的右视图

题目描述

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

示例:

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

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

题解

BFS

在层序遍历的题目中, 在从上到下打印二叉树Ⅱ的基础上, 把每一层的最后一个元素放进一个列表中即可.

因为每到了新的一层, 队列中元素的数量就是该层节点数, 所以可以简单地找出这层最后一个元素.

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null)
        return res;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    TreeNode cur;

    while (!queue.isEmpty()) {
        int levelNums = queue.size();
        for (int i = 0; i < levelNums; i++) {
            cur = queue.poll();
            if (i == levelNums - 1)
                res.add(cur.val);
            if (cur.left!=null)
                queue.add(cur.left);
            if (cur.right!=null)
                queue.add(cur.right);
        }
    }

    return res;
}

DFS

思路： 我们按照 「根结点 -> 右子树 -> 左子树」 的顺序访问，就可以保证每层都是最先访问最右边的节点的。

（与先序遍历 「根结点 -> 左子树 -> 右子树」 正好相反，先序遍历每层最先访问的是最左边的节点）

对于这张图中的情况, 节点8之后并不会直接遍历到节点9, 而是会遍历到节点2, 但是此时递归传递的depth 是1, 而res.size()为4, 所以不会加入到结果列表中, 直到遍历至节点9

class Solution {
    List<Integer> res = new ArrayList<>();

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

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