總結(jié)leetcode75中深度優(yōu)先搜索的算法題解題思路。
上一篇：力扣75——鏈表
以下代碼部分為本人所寫，部分為官方示例代碼。

1 二叉樹的最大深度

題目：

給定一個二叉樹 root ，返回其最大深度。二叉樹的 最大深度 是指從根節(jié)點到最遠(yuǎn)葉子節(jié)點的最長路徑上的節(jié)點數(shù)。

題解：遞歸。

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

2 葉子相似的樹

題目：

請考慮一棵二叉樹上所有的葉子，這些葉子的值按從左到右的順序排列形成一個 葉值序列 。
如果有兩棵二叉樹的葉值序列是相同，那么我們就認(rèn)為它們是 葉相似 的。
如果給定的兩個根結(jié)點分別為 root1 和 root2 的樹是葉相似的，則返回 true；否則返回 false 。

題解：調(diào)用遞歸函數(shù)leafOperate，用r1記錄root1葉子節(jié)點的值，r2記錄root2葉子節(jié)點的值。

 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 統(tǒng)計二叉樹中好節(jié)點的數(shù)目

題目：

給你一棵根為 root 的二叉樹，請你返回二叉樹中好節(jié)點的數(shù)目。「好節(jié)點」X 定義為：從根到該節(jié)點 X 所經(jīng)過的節(jié)點中，沒有任何節(jié)點的值大于 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

題目：

給定一個二叉樹的根節(jié)點 root ，和一個整數(shù) targetSum ，求該二叉樹里節(jié)點值之和等于 targetSum 的 路徑 的數(shù)目。路徑 不需要從根節(jié)點開始，也不需要在葉子節(jié)點結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點到子節(jié)點）。

題解：遞歸。pathSum函數(shù)是計算所有可能的路徑的。rootSum函數(shù)是計算以該節(jié)點開始，可能得路徑的。

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 為根的二叉樹，二叉樹中的交錯路徑定義如下：選擇二叉樹中 任意 節(jié)點和一個方向（左或者右）。
如果前進(jìn)方向為右，那么移動到當(dāng)前節(jié)點的的右子節(jié)點，否則移動到它的左子節(jié)點。
改變前進(jìn)方向：左變右或者右變左。
重復(fù)第二步和第三步，直到你在樹中無法繼續(xù)移動。
交錯路徑的長度定義為：訪問過的節(jié)點數(shù)目 - 1（單個節(jié)點的路徑長度為 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 二叉樹的最近公共祖先

題目：

給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節(jié)點 p、q，最近公共祖先表示為一個節(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）。”

題解：先遞歸，找到每個節(jié)點的父節(jié)點。然后給節(jié)點p的所有祖先節(jié)點打上標(biāo)記，最后查看節(jié)點q祖先節(jié)點中哪個是已經(jīng)打上標(biāo)記的。

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 解題總結(jié)

這些題都是深度優(yōu)先搜索。
基本上深度優(yōu)先搜索都是采用遞歸函數(shù)來實現(xiàn)。
題4比較特殊，它的情況按是否包括當(dāng)前節(jié)點來劃分，所以得有兩個遞歸函數(shù)。