教做甜品网站,信誉好的武进网站建设,企业营销型网站分析,星空无限传媒免费观看电视剧总结leetcode75中深度优先搜索的算法题解题思路。 上一篇#xff1a;力扣75——链表 以下代码部分为本人所写#xff0c;部分为官方示例代码。 力扣75——深度优先搜索 1 二叉树的最大深度2 叶子相似的树3 统计二叉树中好节点的数目4 路径总和 III5 二叉树中的最长交错路径6 …总结leetcode75中深度优先搜索的算法题解题思路。 上一篇力扣75——链表 以下代码部分为本人所写部分为官方示例代码。 力扣75——深度优先搜索 1 二叉树的最大深度2 叶子相似的树3 统计二叉树中好节点的数目4 路径总和 III5 二叉树中的最长交错路径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) {vectorint 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, vectorint 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 nullptrroot-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 nullptrroot-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_mapint, TreeNode* fa;unordered_mapint, 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比较特殊它的情况按是否包括当前节点来划分所以得有两个递归函数。
