题目地址(199. 二叉树的右视图)

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

题目描述

  1. 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
  5. 示例 1:
  7. 输入: [1,2,3,null,5,null,4]
  8. 输出: [1,3,4]
  11. 示例 2:
  13. 输入: [1,null,3]
  14. 输出: [1,3]
  17. 示例 3:
  19. 输入: []
  20. 输出: []
  25. 提示:
  27. 二叉树的节点个数的范围是 [0,100]
  28. -100 <= Node.val <= 100

前置知识


公司

  • 暂无

思路

使用层序遍历 每次将最右边的数据添加到返回数组中

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public List<Integer> rightSideView(TreeNode root) {
  19.             ArrayList<Integer> list = new ArrayList<>();
  20.             //使用双端队列
  21.             Deque<TreeNode> queue = new LinkedList<>();
  22.             if (root == null) {
  23.                 return list;
  24.             }
  25.             queue.offerLast(root);
  26.             while (!queue.isEmpty()) {
  27.                 int size = queue.size();
  28.                 //循环size次 每层的size不同
  29.                 for (int i = 0; i < size; i++) {
  30.                     TreeNode pollFirst = queue.pollFirst();
  31.                     if (pollFirst.left != null) {
  32.                         queue.offerLast(pollFirst.left);
  33.                     }
  34.                     if (pollFirst.right != null) {
  35.                         queue.offerLast(pollFirst.right);
  36.                     }
  37.                     //每层添加的都是队列最右边的数字
  38.                     if (i == size - 1) {
  39.                         list.add(pollFirst.val);
  40.                     }
  41.                 }
  42.             }
  43.             return list;
  44.         }
  45.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：199. 二叉树的右视图 - 图1#card=math&code=O%28n%29&id=MJG0f)
  • 空间复杂度：199. 二叉树的右视图 - 图2#card=math&code=O%28n%29&id=FqTmm)