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

网站统计源码搜索引擎营销的优势

网站统计源码,搜索引擎营销的优势,溧阳网站建设哪家好,广东做陶瓷的网站总结leetcode75中深度优先搜索的算法题解题思路。 上一篇:力扣75——链表 以下代码部分为本人所写,部分为官方示例代码。 力扣75——深度优先搜索 1 二叉树的最大深度2 叶子相似的树3 统计二叉树中好节点的数目4 路径总和 III5 二叉树中的最长交错路径6 …

总结leetcode75中深度优先搜索的算法题解题思路。
上一篇:力扣75——链表
以下代码部分为本人所写,部分为官方示例代码。

力扣75——深度优先搜索

  • 1 二叉树的最大深度
  • 2 叶子相似的树
  • 3 统计二叉树中好节点的数目
  • 4 路径总和 III
  • 5 二叉树中的最长交错路径
  • 6 二叉树的最近公共祖先
  • 1-6 解题总结

1 二叉树的最大深度

题目:

给定一个二叉树 root ,返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

题解:递归。

 class Solution {public:int maxDepth(TreeNode* root) {if (root == nullptr)return 0;else {return 1 + max(maxDepth(root->left), maxDepth(root->right));}}};

2 叶子相似的树

题目:

请考虑一棵二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
如果有两棵二叉树的叶值序列是相同,那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的,则返回 true;否则返回 false

题解:调用递归函数leafOperate,用r1记录root1叶子节点的值,r2记录root2叶子节点的值。

 class Solution {public:bool leafSimilar(TreeNode* root1, TreeNode* root2) {vector<int> r1, r2;if (root1) {if (root1->left || root1->right) {leafOperate(root1->left, r1);leafOperate(root1->right, r1);}else {r1.push_back(root1->val);}		 }if (root2 != nullptr) {if (root2->left || root2->right) {leafOperate(root2->left, r2);leafOperate(root2->right, r2);}else {r2.push_back(root2->val);}}return r1 == r2;}void leafOperate(TreeNode* root, vector<int> &r) {if (root == nullptr) return;else {if (root->left || root->right) {leafOperate(root->left, r);leafOperate(root->right, r);}else {r.push_back(root->val);}}}};

3 统计二叉树中好节点的数目

题目:

给你一棵根为 root 的二叉树,请你返回二叉树中好节点的数目。「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。

题解:递归查找。

class Solution {public:int goodNodes(TreeNode* root) {if (root == nullptr) return 0;if (root->left == nullptr&&root->right == nullptr) return 1;int nums = 1, maxnow = root->val;goodnodes(root->left, nums, maxnow);goodnodes(root->right, nums, maxnow);return nums;}void goodnodes(TreeNode* root, int &nums,int maxnow) {if (root == nullptr) return;if (root->val >= maxnow) {nums++;maxnow = root->val;}if (root->left == nullptr&&root->right == nullptr) return;goodnodes(root->left, nums, maxnow);goodnodes(root->right, nums, maxnow);}};

4 路径总和 III

题目:


给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

题解:递归。pathSum函数是计算所有可能的路径的。rootSum函数是计算以该节点开始,可能得路径的。

class Solution {
public:int rootSum(TreeNode* root, long targetSum) {if (!root) {return 0;}int ret = 0;if (root->val == targetSum) {ret++;} ret += rootSum(root->left, targetSum - root->val);ret += rootSum(root->right, targetSum - root->val);return ret;}int pathSum(TreeNode* root, int targetSum) {if (!root) {return 0;}int ret = rootSum(root, targetSum);ret += pathSum(root->left, targetSum);ret += pathSum(root->right, targetSum);return ret;}
};

5 二叉树中的最长交错路径

题目:

给你一棵以 root 为根的二叉树,二叉树中的交错路径定义如下:选择二叉树中 任意 节点和一个方向(左或者右)。
如果前进方向为右,那么移动到当前节点的的右子节点,否则移动到它的左子节点。
改变前进方向:左变右或者右变左。
重复第二步和第三步,直到你在树中无法继续移动。
交错路径的长度定义为:访问过的节点数目 - 1(单个节点的路径长度为 0 )。请你返回给定树中最长 交错路径 的长度。

题解:递归。

class Solution {
public:int maxAns;/* 0 => left, 1 => right */void dfs(TreeNode* o, bool dir, int len) {maxAns = max(maxAns, len);if (!dir) {if (o->left) dfs(o->left, 1, len + 1);if (o->right) dfs(o->right, 0, 1);} else {if (o->right) dfs(o->right, 0, len + 1);if (o->left) dfs(o->left, 1, 1);}} int longestZigZag(TreeNode* root) {if (!root) return 0;maxAns = 0;dfs(root, 0, 0);dfs(root, 1, 0);return maxAns;}
};

6 二叉树的最近公共祖先

题目:

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

题解:先递归,找到每个节点的父节点。然后给节点p的所有祖先节点打上标记,最后查看节点q祖先节点中哪个是已经打上标记的。

class Solution {
public:unordered_map<int, TreeNode*> fa;unordered_map<int, bool> vis;void dfs(TreeNode* root){if (root->left != nullptr) {fa[root->left->val] = root;dfs(root->left);}if (root->right != nullptr) {fa[root->right->val] = root;dfs(root->right);}}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {fa[root->val] = nullptr;dfs(root);while (p != nullptr) {vis[p->val] = true;p = fa[p->val];}while (q != nullptr) {if (vis[q->val]) return q;q = fa[q->val];}return nullptr;}
};

1-6 解题总结

这些题都是深度优先搜索。
基本上深度优先搜索都是采用递归函数来实现。
题4比较特殊,它的情况按是否包括当前节点来划分,所以得有两个递归函数。

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

相关文章:

  • 做网站需要解析吗苏州seo服务热线
  • 买了个域名 如何自己做网站关键词工具软件
  • wordpress 模版 婚礼东莞seo顾问
  • web网站设计要怎么做竞价账户托管公司哪家好
  • 汉高建设公司网站semen
  • 长沙seo优化首选合肥seo推广培训班
  • 成都响应式网站杭州网站制作排名
  • 做一个中英文双语网站建设多少钱什么叫做关键词
  • 沈阳建设局网站首页个人怎么做网站
  • 做个网站页面多钱武汉网络推广seo
  • 教做美食的网站化工seo顾问
  • 找人做黑彩网站靠谱么软文写作要求
  • 网站建设企业资质百度长尾关键词挖掘工具
  • 乌鲁木齐做网站哪家好推广软文代发
  • 做h5的网站页面设计人民日报新闻消息
  • 搭建一个企业网站打开百度搜索引擎
  • 手机在网上怎么创建自己的网站电脑优化软件推荐
  • 用flash做游戏下载网站宁波网站推广大全
  • 南通水情最新信息东莞快速优化排名
  • 网站建站推荐广州最新疫情情况
  • 建设网站前端seo工具在线访问
  • 中铁建设集团门户网登安卓aso优化
  • 海兴县做网站价格阿里云建站
  • 网站建设计划排名优化网站seo排名
  • 如何做外贸独立网站百度老年搜索
  • 鄂州网站制作西安seo外包平台
  • wordpress布置网站教程职业技能培训班
  • 导购类网站怎么做培训机构哪家好
  • 广告投放的理解seo查询工具
  • 郑州教育培训机构网站建设邳州网站开发