1. 首页
  2. LeetCode 刷题网

LeetCode 199. 二叉树的右视图

题目描述

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

示例:

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

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

难度:Middle

前置知识

  • 队列

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这道题和 leetcode 102 号问题《102.binary-tree-level-order-traversal》很像

这道题可以借助队列实现,首先把 root 入队,然后入队一个特殊元素 Null(来表示每层的结束)。

然后就是 while(queue.length), 每次处理一个节点,都将其子节点(在这里是 left 和 right)放到队列中。

然后不断的出队, 如果出队的是 null,则表式这一层已经结束了,我们就继续 push 一个 null。

关键点解析

  • 队列

  • 队列中用 Null(一个特殊元素)来划分每层

  • 树的基本操作- 遍历 – 层次遍历(BFS)

  • 二叉树的右视图可以看作是层次遍历每次只取每一层的最右边的元素

代码

语言支持:JS,C++

Javascript Code:

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
  if (!root) return [];

  const ret = [];
  const queue = [root, null];

  let levelNodes = [];

  while (queue.length > 0) {
    const node = queue.shift();
    if (node !== null) {
      levelNodes.push(node.val);
      if (node.right) {
        queue.push(node.right);
      }
      if (node.left) {
        queue.push(node.left);
      }
    } else {
      // 一层遍历已经结束
      ret.push(levelNodes[0]);
      if (queue.length > 0) {
        queue.push(null);
      }
      levelNodes = [];
    }
  }

  return ret;
};

C++ Code:

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        auto ret = vector<int>();
        if (root == nullptr) return ret;
        auto q = queue<const TreeNode*>();
        q.push(root);
        while (!q.empty()) {
            auto sz = q.size();
            for (auto i = 0; i < sz; ++i) {
                auto n = q.front();
                q.pop();
                if (n->left != nullptr ) q.push(n->left);
                if (n->right != nullptr ) q.push(n->right);
                if (i == sz - 1) ret.push_back(n->val);
            }
        }
        return ret;
    }
};

扩展

假如题目变成求二叉树的左视图呢?

很简单我们只需要取 queue 的最后一个元素即可。 或者存的时候反着来也行

其实我们没必要存储 levelNodes,而是只存储每一层最右的元素,这样空间复杂度就不是 n 了, 就是 logn 了。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 199. 二叉树的右视图

链接:https://www.javascriptc.com/4540.html

« LeetCode 200. 岛屿数量
重新思考 Redux»
Flutter 中文教程资源

相关推荐

QR code