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

四川省住房与城乡建设厅网站管网云搜索网页版入口

四川省住房与城乡建设厅网站管网,云搜索网页版入口,打开网站是iis7,最好的网页设计公司513. 找树左下角的值 给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 思路:找到最低层中最左侧的节点值,比较适合层序遍历,返回最…

513. 找树左下角的值

给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1

思路:找到最低层中最左侧的节点值,比较适合层序遍历,返回最低层的第一个值即可。

细节:判断是否是最低层,需要保存节点的当前层数。可以用queue<pair>来保存pair保存<节点指针,层数>

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int findBottomLeftValue(TreeNode* root) {if(!root) return -1;queue<pair<TreeNode*,int>> q;q.push({root,1});int deepthMax=1;int ret=root->val;while(!q.empty()){pair<TreeNode*,int> pariFront=q.front();TreeNode* nodeFront=pariFront.first;int deepth=pariFront.second;//判断是否是更低的一层if(deepth>deepthMax){deepthMax=deepth;ret=nodeFront->val;}q.pop();if(nodeFront->left) q.push({nodeFront->left,deepth+1});if(nodeFront->right) q.push({nodeFront->right,deepth+1});}return ret;}
};
  • 时间复杂度:O(n),其中 nnn 是二叉树的节点数目。



654. 最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点,其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 

示例 1:

输入:nums = [3,2,1,6,0,5]
输出:[6,3,5,null,2,0,null,null,1]
解释:递归调用如下所示:
- [3,2,1,6,0,5] 中的最大值是 6 ,左边部分是 [3,2,1] ,右边部分是 [0,5] 。- [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。- 空数组,无子节点。- [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。- 空数组,无子节点。- 只有一个元素,所以子节点是一个值为 1 的节点。- [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。- 只有一个元素,所以子节点是一个值为 0 的节点。- 空数组,无子节点。

 思路:最简单的方法是直接按照题目描述进行模拟。

左子树为 construct(nums,left,best−1)

右子树为 construct(nums,best+1,right)

当递归到一个空数组时,便可以返回一棵空的树。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int findMaxIndex(vector<int>& nums){int ret=0;for(int i=1;i<nums.size();i++){if(nums[i]>nums[ret]) ret=i;}return ret;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.empty()) return nullptr;int maxIndex=findMaxIndex(nums);vector<int> leftNums(nums.begin(),nums.begin()+maxIndex);vector<int> rightNums(nums.begin()+maxIndex+1,nums.end());TreeNode* root=new TreeNode(nums[maxIndex],constructMaximumBinaryTree(leftNums), //左子树constructMaximumBinaryTree(rightNums)); //右子树return root;}
};

时间复杂度:O(n^2),其中 nnn 是数组 nums\textit{nums}nums 的长度。在最坏的情况下,数组严格递增或递减,需要递归 n 层,第 i (0≤i<n)层需要遍历 n−i个元素以找出最大值,总时间复杂度为 O(n2)

思路2:利用单调栈可以实现时间复杂度O(n)

代码随想录

http://www.zhongyajixie.com/news/16955.html

相关文章:

  • 大连甘井子区房价安卓优化大师app下载安装
  • wordpress自动跳转https广州seo黑帽培训
  • 建设门户网站自媒体十大平台
  • 台州网站哪家专业线上推广引流渠道
  • 源代码查看WordPress文件郑州seo公司排名
  • 软件开发公司需要什么硬件设备班级优化大师网页版
  • 网上有兼职做数据网站2023年第三波新冠9月
  • 汽车logo设计图片创意长沙正规seo优化公司
  • 在郑州做网站网络优化工程师有多累
  • 用手机搭建自己的网站海南百度推广代理商
  • 哪个网站做免费小程序seo推广服务哪家好
  • 网站做301顶级域名需要绑定百度在线提问
  • 廊坊网站建设推广服务企业网络营销
  • 网站页面如何设计企业网站设计制作
  • 浙江网站建设推广公司哪家权威《新闻联播》 今天
  • 建设单位网站经费请示企业文化标语经典
  • 美国做爰直播网站中国新闻最新消息今天
  • 做网站合同模板怎么优化电脑系统
  • 昆明专业网站设计公司四川seo优化
  • 政府网站什么程序做的网络营销期末考试试题及答案
  • 音乐网站怎么做外链地推接单平台
  • 加强门户网站建设的方案今天百度数据
  • 做网站起诉线上广告推广平台
  • 手机网站可以做英文版本吗网站友情链接的好处
  • 广州专业网站建设后台管理便捷百度竞价排名费用
  • fontawesome wordpresswindows清理优化大师
  • 武义县网站制作如何开发软件app
  • 业余做衣服的网站哈尔滨seo公司
  • 网站建设销售客户疑问nba最新新闻
  • 中企动力主要做什么的上海谷歌seo公司