题目描述
给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
示例:
输入: [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 了。
- 原题leetcode链接:https://leetcode-cn.com/problems/binary-tree-right-side-view/
- 更多力扣 解题: 力扣 – 全球极客挚爱的技术成长平台 ,也可以访问我的 JS中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books,标星关注一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com