题目描述（中等难度）

199. Binary Tree Right Side View - 图1

给一个二叉树，然后想象自己站在二叉树右边向左边看过去，返回从上到下看到的数字序列。

解法一

题目意思再说的直白一些，就是依次输出二叉树每层最右边的元素。

每层最右边，可以想到二叉树的层次遍历，我们只需要保存每层遍历的最后一个元素即可。

二叉树的层次遍历在 102 题 已经做过了，代码拿过来用就可以。

我们只需要用一个队列，每次保存下层的元素即可。

  1. public List<Integer> rightSideView(TreeNode root) {
  2.     Queue<TreeNode> queue = new LinkedList<TreeNode>();
  3.     List<Integer> res = new LinkedList<>();
  4.     if (root == null)
  5.         return res;
  6.     queue.offer(root);
  7.     while (!queue.isEmpty()) {
  8.         int levelNum = queue.size(); // 当前层元素的个数
  9.         for (int i = 0; i < levelNum; i++) {
  10.             TreeNode curNode = queue.poll();
  11.             //只保存当前层的最后一个元素
  12.             if (i == levelNum - 1) {
  13.                 res.add(curNode.val);
  14.             }
  15.             if (curNode.left != null) {
  16.                 queue.offer(curNode.left);
  17.             }
  18.             if (curNode.right != null) {
  19.                 queue.offer(curNode.right);
  20.             }
  22.         }
  23.     }
  24.     return res;
  25. }

解法二

解法一的层次遍历是最直接的想法。我们也可以用深度优先遍历，在 这里) 看到的。

二叉树的深度优先遍历在之前也讨论过了， 94 题 的中序遍历、 144 题 的先序遍历以及 145 题 的后序遍历。

这里采用最简单的递归写法，并且优先从右子树开始遍历。

用一个变量记录当前层数，每次保存第一次到达该层的元素。

  1. public List<Integer> rightSideView(TreeNode root) {
  2.     List<Integer> res = new LinkedList<>();
  3.     rightSideViewHelper(root, 0, res);
  4.     return res;
  5. }
  7. private void rightSideViewHelper(TreeNode root, int level, List<Integer> res) {
  8.     if (root == null) {
  9.         return;
  10.     }
  11.     //res.size() 的值理解成当前在等待的层级数
  12.     //res.size() == 0, 在等待 level = 0 的第一个数
  13.     //res.size() == 1, 在等待 level = 1 的第一个数
  14.     //res.size() == 2, 在等待 level = 2 的第一个数
  15.     if (level == res.size()) {
  16.         res.add(root.val);
  17.     }
  18.     rightSideViewHelper(root.right, level + 1, res);
  19.     rightSideViewHelper(root.left, level + 1, res);
  20. }

总

这道题其实本质上就是考了二叉树的层次遍历和深度优先遍历。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情