SlovinG
Search K

Appearance

199.二叉树的右视图 ​

难度：中等

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

示例 1:

img

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

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

提示:

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

广度优先搜索法（BFS） ​

这道题和 102 题很类似，改动在于在每一层的遍历过程中，需要判断当前是否遍历到了本层的最后一个元素，如果是，才将其放进 result 列表中。

层序遍历一个二叉树。就是从左到右、一层一层地去遍历二叉树。这种遍历的方式需要借用一个辅助数据结构即队列来实现。

队列具有 先进先出 的特性，符合层序遍历的逻辑。这种层序遍历的方式就是图论中的广度优先遍历，只不过我们应用在了二叉树上。

算法流程：

  1. 处理特例：若根节点为空，则返回空列表

  2. 根节点入队

  3. BFS 循环： 判断队列是否为空。如果不为空，说明还有节点需要遍历

    1. 初始化当前层的节点个数 currentLevelSize 为队列的大小。
    2. 使用一个内层循环，遍历当前层的节点。循环次数为当前层的节点个数 currentLevelSize。
      1. 从队列中取出一个节点 current，判断其是否是当前层的最后一个元素，若是，则将其值添加到结果列表 result 中。
      2. 如果当前节点有左子节点，将左子节点入队。
      3. 如果当前节点有右子节点，将右子节点入队。
    3. 此时队列中已经把当前层的节点都出队了，同时把下一层的节点都入队了，因此队列大小刚好变成了下一层的节点个数。

  4. 返回结果列表

代码展示 ​

java
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    // 若根节点为空，则返回空列表
    if (root == null) {
        return result;
    }
    Deque<TreeNode> queue = new LinkedList<>();
    // 根节点入队
    queue.add(root);
    // BFS 循环
    while (!queue.isEmpty()) {
        int currentLayerSize = queue.size();
        // 这里一定要使用固定大小currentLayerSize，不要使用queue.size()，因为queue不停地出队入队，所以其大小是不断变化的
        for (int i = 0; i < currentLayerSize; i++) {
            TreeNode current = queue.poll();
            // 将当前层的最后一个节点放入结果列表
            if (i == currentLayerSize - 1) {
                result.add(current.val);
            }
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
    }
    return result;
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，最差情况下，即当树为满二叉树时，最多有 (n+1)/2 个树节点 同时 在 queue 中，故使用 O(n) 大小的额外空间。

总结 ​

在链表头部插入数据的时间复杂度是 O(1)。