【leetcode】DFS递归题目总结

DFS（深度优先搜索）深度优先搜索是一种用于遍历或搜索树或图的算法，其基本思路是从起始节点开始，沿着一条路径一直走到底，直到无法再走下去为止，然后回溯到上一个节点，继续走到另外一个路径，重复上述过程，直到遍历完所有节点。

dfs框架：

void dfs(int cur, vector<int>& visited, vector<vector<int>>& graph) {visited[cur] = 1; // 标记当前节点已经被访问// 处理当前节点curfor (int i = 0; i < graph[cur].size(); i++) {int next = graph[cur][i];if (!visited[next]) { // 如果下一个节点未被访问dfs(next, visited, graph); // 继续访问下一个节点}}
}
void dfsTraversal(vector<vector<int>>& graph) {int n = graph.size();vector<int> visited(n, 0); // 初始化访问数组for (int i = 0; i < n; i++) {if (!visited[i]) { // 如果当前节点未被访问dfs(i, visited, graph); // 从当前节点开始进行深度优先遍历}}
}

94. 二叉树的中序遍历

/*** 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> res;void traversal(TreeNode* root) {if (root == nullptr) return;traversal(root->left);res.push_back(root->val);traversal(root->right);}vector<int> inorderTraversal(TreeNode* root) {traversal(root);return res;}
};

104. 二叉树的最大深度

/*** 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:int maxDepth(TreeNode* root) {if (root == nullptr) return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;}
};

226. 翻转二叉树

/*** 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:void travsal(TreeNode* root) {if (root == nullptr) return;TreeNode* temp = root->right;root->right = root->left;root->left = temp;travsal(root->left);travsal(root->right);}TreeNode* invertTree(TreeNode* root) {travsal(root);return root;}
};

101. 对称二叉树

/*** 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:bool dfs(TreeNode* left, TreeNode* right) {if (left == nullptr && right == nullptr) {return true;}if (left == nullptr || right == nullptr) {return false;}if (left->val != right->val) {return false;}return dfs(left->left, right->right) && dfs(left->right, right->left);}bool isSymmetric(TreeNode* root) {return dfs(root, root);}
};

543. 二叉树的直径

/*** 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:int resDiameter = 0;int maxDepth(TreeNode* root) {if (root == nullptr) return 0;int maxLeft = maxDepth(root->left);int maxRight = maxDepth(root->right);int curDiameter = maxLeft + maxRight;resDiameter = max(curDiameter, resDiameter);return max(maxLeft, maxRight) + 1;}int diameterOfBinaryTree(TreeNode* root) {maxDepth(root);return resDiameter;}
};

200. 岛屿数量

class Solution {
public:void dfs(vector<vector<char>>& grid, int i, int j) {int m = grid.size();int n = grid[0].size(); if (i < 0 || j < 0 || i >= m || j >= n) {return;}if (grid[i][j] == '0') {return;}if (grid[i][j] == '1') {grid[i][j] = '0';dfs(grid, i, j - 1);dfs(grid, i, j + 1);dfs(grid, i - 1, j);dfs(grid, i + 1, j);}}int numIslands(vector<vector<char>>& grid) {int m = grid.size();int n = grid[0].size(); int res = 0;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == '1') {res += 1;dfs(grid, i, j);} }}return res;}
};

LCR 054. 把二叉搜索树转换为累加树

/*** 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:int sum = 0;void travesal(TreeNode* root) {if (root == nullptr) return;travesal(root->right);sum += root->val;root->val = sum;travesal(root->left);}TreeNode* convertBST(TreeNode* root) {travesal(root);return root;}
};

98. 验证二叉搜索树

/*** 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:bool myIsValidBST(TreeNode* root, long long min, long long max) {if (root == nullptr) return true;if (root->val <= min || root->val >= max) return false;return myIsValidBST(root->left, min, root->val) && myIsValidBST(root->right, root->val, max);}bool isValidBST(TreeNode* root) {return myIsValidBST(root, LLONG_MIN, LLONG_MAX);}
};

700. 二叉搜索树中的搜索

/*** 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:TreeNode* searchBST(TreeNode* root, int val) {if (root == nullptr) return nullptr;if (root->val == val) return root;return root->val > val ? searchBST(root->left, val) : searchBST(root->right, val);}
};

199. 二叉树的右视图

/*** 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> res;void dfs(TreeNode* root, int depth) {if (root == nullptr) return;if (depth == res.size()) {res.push_back(root->val);}depth++;dfs(root->right, depth);dfs(root->left, depth);}vector<int> rightSideView(TreeNode* root) {dfs(root, 0);return res;}
};

236. 二叉树的最近公共祖先

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (!root) return NULL;if (root == p) return p;if (root == q) return q;TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);if (left && right) return root;return left ? left : right; }
};

111. 二叉树的最小深度

class Solution {
public:int minDepth(TreeNode *root) {if (root == nullptr) {return 0;}if (root->left == nullptr && root->right == nullptr) {return 1;}int min_depth = INT_MAX;if (root->left != nullptr) {min_depth = min(minDepth(root->left), min_depth);}if (root->right != nullptr) {min_depth = min(minDepth(root->right), min_depth);}return min_depth + 1;}
};

104. 二叉树的最大深度

/*** 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:int maxDepth(TreeNode* root) {if (root == nullptr) return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;}
};

124. 二叉树中的最大路径和

/*** 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:int maxSum = INT_MIN;int maxGain(TreeNode* root) {if (root == nullptr) return 0;int left = max(maxGain(root->left), 0);int right = max(maxGain(root->right), 0);int cur = root->val + left + right;maxSum = max(cur, maxSum);return root->val + max(left, right);}int maxPathSum(TreeNode* root) {maxGain(root);return maxSum;}
};

230. 二叉搜索树中第K小的元素

/*** 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:int index = 0;int res = 0;void travesal(TreeNode* root, int k) {if (root == nullptr) return;travesal(root->left, k);if (++index == k) {res = root->val;return;}travesal(root->right, k);}int kthSmallest(TreeNode* root, int k) {travesal(root, k);return res;}
};

652. 寻找重复的子树

/*** 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:unordered_map<string, int> seen;vector<TreeNode*> res;string travesal(TreeNode* root) {if (root == nullptr) return "#";string left = travesal(root->left);string right = travesal(root->right);string subTree = left + "," + right + "," + to_string(root->val);auto it = seen.find(subTree);if (it != seen.end() && it->second == 1) {res.push_back(root);}seen[subTree]++;return subTree;}vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {travesal(root);return res;}
};