力扣75——深度优先搜索

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

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比较特殊，它的情况按是否包括当前节点来划分，所以得有两个递归函数。