当前位置: 首页 > news >正文

网站支付接口怎么做百度云网盘登录入口

网站支付接口怎么做,百度云网盘登录入口,web网站制作软件,商场设计师Problem: 199. 二叉树的右视图 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路 无论是DFS还是BFS我们都要思考到达二叉树的每一层(或者每一层中的每一个节点)时,我们都该如何按题目要求做出对应得处理!!!在本体中我们主要是&#x…

Problem: 199. 二叉树的右视图

文章目录

  • 题目描述
  • 思路
  • 解题方法
  • 复杂度
  • Code

题目描述

在这里插入图片描述在这里插入图片描述

思路

无论是DFS还是BFS我们都要思考到达二叉树的每一层(或者每一层中的每一个节点)时,我们都该如何按题目要求做出对应得处理!!!在本体中我们主要是:

1.当右子树与左子树等高或者右子树高于左子树时,我们只添加每一个右子树得右节点到结果集(根节点得左子树整个都去除)
2.当左子树高于右子树时,我们将等高得部分按1中处理,左子树高出右子树得部分,再将其右子树得右节点添加到结果集

解题方法

思路1:DFS

1.创建unordered_map<int, int> rightmostValueAtDepth;记录每一层应该添加到右视图的节点,int maxDepth = -1;记录并维护当前的最大深度,stack<TreeNode > nodeStack;用于DFS过程中的存储节点,stack depthStack;用于同时记录DFS过程中的树的深度;
2.将根节点添加到nodeStack中,while循环遍历(循环退出条件为nodeStack为空),每次弹出nodeStack和depthStack中的栈顶元素
node
depth
,若此时
node不为空
则更新最大深度,同时
若rightmostValueAtDepth[depth]不存在则添加到rightmostValueAtDepth中*;并且将node -> left;node -> right;depth + 1;depth + 1分别添加到对应的nodeStack和depthStack栈
3.最后将rightmostValueAtDepth中的值添加到一个一维数组中即可

思路2:BFS
大体实现直接套用BFS代码的模板书写即可,具体解释下面代码实现中的两个点

1.由于常规的BFS模板均是先添加左子树节点到队列,再添加右子树节点到队列所以我们可以利用数组元素可以覆盖的特性在每次添加节点到队列时,也将该节点值放入一个空间大小为1的数组temp中,这样操作后无论是思路中1、2哪种情况,都能保证最后添加到结果集中的节点值是复合题目右视图这个定义;
2.按常规BFS代码的实现(或者说就是按下面代码前面部分的操作)会导致最后一个被写到temp数组中的元素会添加两次到最终的结果集中,所以要push_back一次!!!

复杂度

思路1、2均如下
时间复杂度:

O ( n ) O(n) O(n)

空间复杂度:

O ( n ) O(n) O(n)

Code

思路1:

class Solution {
public:/*** DFS** @param root The root of a binary tree* @return vector<int>*/vector<int> rightSideView(TreeNode *root) {if (root == nullptr) {return {};}unordered_map<int, int> rightmostValueAtDepth;int maxDepth = -1;stack<TreeNode *> nodeStack;stack<int> depthStack;nodeStack.push(root);depthStack.push(0);while (!nodeStack.empty()) {TreeNode *node = nodeStack.top();nodeStack.pop();int depth = depthStack.top();depthStack.pop();if (node != nullptr) {//Maintain the maximum depth of a binary treemaxDepth = max(maxDepth, depth);//If not in the map collection, add itif (rightmostValueAtDepth.find(maxDepth) == rightmostValueAtDepth.end()) {rightmostValueAtDepth[depth] = node->val;}nodeStack.push(node->left);nodeStack.push(node->right);depthStack.push(depth + 1);depthStack.push(depth + 1);}}vector<int> res;for (int i = 0; i < maxDepth; ++i) {res.push_back(rightmostValueAtDepth[i]);}return res;}
};

思路2:

class Solution {
public:/*** BFS* * @param root The root of a binary tree* @return vector<int>*/vector<int> rightSideView(TreeNode* root) {if (root == nullptr) {return {};}if (root -> left == nullptr && root -> right == nullptr) {return {root -> val};}vector<int> res;vector<int> temp(1);queue<TreeNode*> queue;res.push_back(root -> val);queue.push(root);while (!queue.empty()) {int curLevelSize = queue.size();for (int i = 0; i < curLevelSize; ++i) {TreeNode* curLevelNode = queue.front();queue.pop();if (curLevelNode -> left != nullptr) {temp[0] = curLevelNode -> left -> val;queue.push(curLevelNode -> left);}if (curLevelNode -> right != nullptr) {temp[0] = curLevelNode -> right -> val;queue.push(curLevelNode -> right);}}res.push_back(temp[0]);}//Pop the last repetitive noderes.pop_back();return res;}
};
http://www.ds6.com.cn/news/24560.html

相关文章:

  • 做网页怎么在网站播放视频百度关键词优化曝光行者seo
  • delphi intraweb做网站成人职业技能培训班
  • 网上书城网站开发的数据字典国内优秀网页设计赏析
  • 郑州网官网东莞优化网站关键词优化
  • 品牌网站建设专业竞价托管
  • 产品网站开发计划表企业域名查询
  • 广州 餐饮 网站建设上海关键词seo
  • 传媒网站建设网seo视频教程我要自学网
  • 汉源县建设局网站搜外滴滴友链
  • 贸易公司网址大全哪些行业适合做seo
  • 物流网站怎么做推广独立站seo外链平台
  • 做淘宝客网站要申请什么小红书代运营
  • 如何在720云网站做全景视频下载发布任务注册app推广的平台
  • 怎样打开用sql做的网站北京seo公司
  • 深圳自适应网站开发多少钱免费企业建站
  • 做网站需要买ip地址吗搜索广告是什么意思
  • 网站开发网站开发设计中国万网官网登录
  • 乐山网站制作公司seo网站制作优化
  • 做微信平台图片网站小程序搭建教程
  • 做面包的网站推广网站免费
  • python写网页西安seo优化培训机构
  • 做微网站哪家好深圳做seo有哪些公司
  • 宝安中心做网站多少钱南宁网站优化公司电话
  • 哪家企业的网站做的好电商网站平台有哪些
  • 自建网站的优缺点微商软文范例大全100
  • 合肥网版制作seo对网络推广的作用是什么?
  • 支付网站认证费用怎么做分录2024年阳性最新症状
  • 公共资源交易中心是事业单位吗济南seo整站优化价格
  • 有没有做维修的网站营销云
  • 网站服务器暂时不可用怎么办企业门户网站模板