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

深圳做网站哪里好seo有哪些优缺点?

深圳做网站哪里好,seo有哪些优缺点?,seo优化教程自学,做网页的网站叫什么软件阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路 二叉树的问题首先我们要想想是否能用递归来解决,本题也不例外,而递归的关键是找到子问题。 我们首先来看看一棵最简单的树,也就是示例 1。这样的一棵树总共有六条路径&#xf…

阅读目录

    • 1. 题目
    • 2. 解题思路
    • 3. 代码实现

1. 题目

2. 解题思路

二叉树的问题首先我们要想想是否能用递归来解决,本题也不例外,而递归的关键是找到子问题。

我们首先来看看一棵最简单的树,也就是示例 1。这样的一棵树总共有六条路径,分别是:根节点、左节点-根节点、右节点-根节点、左节点、右节点、左节点-根节点-右节点,我们用一个大小为 6 的数组 rootSum 来分别表示这六条路径的路径和,那么所求的最大路径和即为 rootSum 的最大值。

需要注意,当某一个节点为空的时候,比如左节点为空,那么左节点-根节点路径和为根节点的值,左节点贡献值为 0。而单独左节点的路径不存在,路径和应该设置为一个极大的负值

接下来,我们再考虑一个更复杂的树,这棵树的根节点有左右两棵子树,每一棵子树都是类似上面示例 1 的一棵树。那么,我们可以很容易地得到左右子树的路径和数组 leftSumrightSum ,接下来,我们要做的就是如何根据这两个数组得到整棵树的路径和数组 rootSum

rootSum 仍然有 6 条路径,其中:

  • 只有一个根节点的路径,rootSum[0]=root->val
  • 左节点-根节点的路径,这时候由于左节点是一棵子树,所以,只有包含子树中根节点的路径才能继续和当前的根节点组成新的路径,也就是子树的前三条路径,然后我们取其中最大的一条即可,rootSum[1]=root->val + max(leftSum[0:3))
  • 右节点-根节点的路径,这个和上面的类似,rootSum[2]=root->val + max(rightSum[0:3))
  • 左节点,也即是单独左子树组成的最大路径,rootSum[3]=max(leftSum[0:6))
  • 右节点,也即是单独右子树组成的最大路径,rootSum[4]=max(rightSum[0:6))
  • 左节点-根节点-右节点,也就是左子树的路径包含左子树的根节点,右子树的路径包含右子树的根节点,rootSum[5]=max(leftSum[0:3))+ root->val + max(rightSum[0:3))

时间复杂度为 O ( n ) O(n) O(n) n n n 代表节点总数,每个节点都需要进行遍历一次,空间复杂度为 O ( n ) O(n) O(n),每个节点都需要存储 6 个状态值。

3. 代码实现

/*** 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:vector<int> getNodePathSum(TreeNode* root) {int leftRootSum = 0, leftMaxSum = -10000;if (root->left != nullptr) {vector<int> leftSum = getNodePathSum(root->left);leftRootSum = *std::max_element(leftSum.begin(), leftSum.begin() + 3);leftMaxSum = *std::max_element(leftSum.begin(), leftSum.end());}int rightRootSum = 0, rightMaxSum = -10000;if (root->right != nullptr) {vector<int> rightSum = getNodePathSum(root->right);rightRootSum = *std::max_element(rightSum.begin(), rightSum.begin() + 3);rightMaxSum = *std::max_element(rightSum.begin(), rightSum.end());}vector<int> rootSum(6, 0);rootSum[0] = root->val;rootSum[1] = leftRootSum + root->val;rootSum[2] = rightRootSum + root->val;rootSum[3] = leftMaxSum;rootSum[4] = rightMaxSum;rootSum[5] = leftRootSum + root->val + rightRootSum;return rootSum;}int maxPathSum(TreeNode* root) {vector<int> sum = getNodePathSum(root);return *std::max_element(sum.begin(), sum.end());}
};
http://www.ds6.com.cn/news/117812.html

相关文章:

  • java如何网站开发百度网盘搜索神器
  • 百度给做网站收费多少钱seo优化交流
  • 高新区微网站建设shodan搜索引擎
  • 软文营销网站浙江百度代理公司
  • 即墨哪里有做网站的上海小红书seo
  • 青浦建设机械网站市场调研报告的基本框架
  • 湖北高端网站建设阿里云云服务平台
  • 如何备份网站网络营销活动推广方式
  • 影视动画专业要学什么汕头seo推广外包
  • 设计网站公司可去亿企邦衡阳有实力seo优化
  • 做个人网站需要多少钱昆明网站seo服务
  • 陕西网站制作商互联网营销推广公司
  • 网站 廉政建设 板块绍兴seo网站推广
  • 电子商务网站开发设计报告书跨境电商培训机构哪个靠谱
  • 网站多少钱一年武汉网站推广公司排名
  • 自己做网站打不开是怎么回事排名优化网站
  • 峰峰专业做网站网站推广论坛
  • 密云区住房和城乡建设委员会网站6河南网站优化排名
  • 静态网站设计模板百度推广账户优化方案
  • 潍坊专业网站建设价格低百度百度一下你就知道主页
  • 环境设计专业必看网站百度怎么发免费广告
  • 永川网站建设百度联盟怎么加入
  • 怎样设计一个网站平台企业营销策划包括哪些内容
  • 酒店网站建设策划书每日军事新闻
  • 做同城信息类网站如何赚钱比较开放的浏览器
  • 做网站设计制作的seo网站结构优化
  • 东莞响应式网站制作爱站网长尾关键词挖掘工具下载
  • 做网站必须要注册公司么公司网站免费建站
  • shopify建站教程苏州旺道seo
  • 南宁 做网站桂林市天气预报