【leetcode】DFS递归题目总结

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

dfs框架：

void dfs(int cur, vector<int>& visited, vector<vector<int>>& graph) {
    visited[cur] = 1; // 标记当前节点已经被访问
    // 处理当前节点cur
    for (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;
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/603289.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【C++】——内存管理

【C++】——内存管理

&#x1f600;&#x1f600;前言 好久没更新了&#xff0c;五一小长假&#xff0c;有点玩脱了&#xff0c;今天赶紧补一篇博客&#xff0c;回回状态 一 c/c内存分配 下面看下面一段代码 #define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> using namespace std; i…
阅读更多...
华为eNSP中型企业局域网网络规划设计（上）

华为eNSP中型企业局域网网络规划设计（上）

敲半天一个闪退全™给我干没了呜呜呜&#xff0c;eNSP&#xff0c;wcnm&#xff01;wcnm&#xff01;wcnm&#xff01; →b站传送门&#xff0c;感谢大佬← →华为eNSP中型企业局域网网络规划设计&#xff08;下&#xff09;← →拓扑图传送门&#xff0c;可以自己配置着玩←…
阅读更多...
抖音小店怎么运营？最全的运营攻略来了？

抖音小店怎么运营？最全的运营攻略来了？

大家好&#xff0c;我是电商糖果 很多开好店铺的小伙伴&#xff0c;都会遇到一个难题&#xff0c;那就是不会运营店铺。 可能好几个月才出十几单&#xff0c;甚至体验分都没有弄出来。 说实话&#xff0c;这种情况糖果见多了。 糖果做抖音小店也有四年多了&#xff0c;也开…
阅读更多...
【全开源】Java淘宝客多商户系统APP源码任务聚合优惠券多商户源码

【全开源】Java淘宝客多商户系统APP源码任务聚合优惠券多商户源码

功能特点&#xff1a; 商户管理&#xff1a;支持多商户入驻&#xff0c;包括商户的注册、审核、信息维护等功能。同时&#xff0c;系统可以对商户进行分类、排序和搜索&#xff0c;方便管理。全行业覆盖√ miui52086商品管理&#xff1a;提供商品发布、编辑、上下架等功能&…
阅读更多...
PMP考试没过怎么办？如何补考？（附复核流程）

PMP考试没过怎么办？如何补考？（附复核流程）

最近刷小红书&#xff0c;看很多人都在晒PMP通过的成绩截图&#xff0c;一方面为大家开心&#xff0c;终于拿到了期盼已久的PMP&#xff0c;但同时也有宝子发挥失常没通过考试&#xff0c;所以这期针对没考过的宝子们&#xff0c;出一期复盘文章&#xff0c;无论结果如何&#…
阅读更多...
QT4-升级到QT5（1）

QT4-升级到QT5（1）

1.C报错汇总_nafxcwd.lib error lnk2001-CSDN博客1 1.QT3Support QWidget::setShown 改为QWidget::setVisible 2.头文件 #include<QWidget> 3.部分函数替换
阅读更多...
印章常见问题如何防？君子签电子印章实现管章、用章、控章一体化

印章常见问题如何防？君子签电子印章实现管章、用章、控章一体化

企业公章管理和使用关乎企业经营&#xff0c;近年来&#xff0c;各类印章问题层出不穷&#xff1a;“通过PS、图片章伪造授权、合同等文件”、“冒充公司员工利用假身份、假印章签约”、“管理层私刻印章伪造业务材料”等常见假印章套路&#xff0c;让企业防不胜防&#xff0c;…
阅读更多...
内网渗透（二）

内网渗透（二）

预备知识 什么是域&#xff1f; 域是若干台计算机组成的集合&#xff0c;一个电脑也是。域中的电脑是分等级的&#xff0c;分为域控和成员机。 如何安装域&#xff1f; 在服务器管理中添加服务器角色&#xff0c;添加域服务 如何加入域? 首先一定要修改DNS服务器 ip为域…
阅读更多...
解密某游戏的数据加密

解密某游戏的数据加密

前言 最近有个兄弟通过我的视频号加我&#xff0c;咨询能否将这个dubo游戏游戏开始前就将数据拿到从而进行押注&#xff0c;于是通过抓包工具测试了下&#xff0c;发现数据有时候是明文&#xff0c;有时候确实密文&#xff0c;大致看了下有这几种加密&#xff1a;Md5aes、Md5&a…
阅读更多...
squeeze的用法

squeeze的用法

squeeze是压缩张量的命令 import torch a torch.randn(1,3) print(a) print(a.shape) 比如说squeeze&#xff08;&#xff1f;&#xff09;括号里是啥 就是在哪个维度上删除维度为1 之后的结果 比如上上面那个里子 a是&#xff08;[[]]&#xff09; 但是在下面那个例子中d…
阅读更多...
软胶囊弹性检测：确保药品质量与患者安全的关键步骤

软胶囊弹性检测：确保药品质量与患者安全的关键步骤

软胶囊弹性检测&#xff1a;确保药品质量与患者安全的关键步骤 在医药领域&#xff0c;软胶囊作为一种常见的药物载体&#xff0c;其质量的优劣直接关系到药物的有效性和患者的安全。软胶囊的弹性作为其质量评估的重要指标之一&#xff0c;不仅影响其储存和运输的稳定性&#x…
阅读更多...
社交客户关系管理（SCRM），和传统CRM的区分

社交客户关系管理（SCRM），和传统CRM的区分

一、SCRM是什么 SCRM是社交客户关系管理&#xff08;Social Customer Relationship Management&#xff09;的缩写&#xff0c;是指通过利用社交媒体和社交网络来管理和建立与客户之间的关系。SCRM将传统的客户关系管理&#xff08;CRM&#xff09;与社交媒体的互动和数据整合…
阅读更多...
vue+sortablejs来实现列表拖拽——sortablejs的使用

vue+sortablejs来实现列表拖拽——sortablejs的使用

sortablejs官网:https://sortablejs.com/ 最近在看form-builder组件&#xff0c;发现里面有用到sortablejs插件&#xff0c;用于实现拖拽效果。 但是这个官网中的配置&#xff0c;实在是看不懂&#xff0c;太简单又太复杂&#xff0c;不实用。 下面记录一下我的使用&#xff…
阅读更多...
光伏设计的核心要素有哪些？

光伏设计的核心要素有哪些？

光伏设计是可再生能源领域中的一个重要分支&#xff0c;它涉及到将太阳能转换为电能的整个过程。在光伏系统的设计和构建过程中&#xff0c;有几个核心要素需要被充分考虑和精确计算&#xff0c;以确保系统的性能、可靠性和经济效益。 一、光照条件分析 光照条件是光伏系统设计…
阅读更多...
Qwen大模型实践之初体验

Qwen大模型实践之初体验

Qwen大模型实践之初体验 测试机器, 使用InternStudio提供的开发机&#xff0c;配置如下&#xff1a; 部分资源详细信息&#xff1a; # CPUIntel(R) Xeon(R) Platinum 8369B CPU 2.90GHz# GPU(base) rootintern-studio-50014188:~# studio-smi Running studio-smi by vgpu-smiW…
阅读更多...
测评方式揭秘：自养号测评与真人测评的利与弊

测评方式揭秘：自养号测评与真人测评的利与弊

在当今电商行业飞速发展的背景下&#xff0c;不少卖家为了提升产品销量和积累良好评价&#xff0c;采取了真人测评和自养号测评两种策略。然而&#xff0c;这两种测评方式的具体运作机制和效果差异&#xff0c;许多卖家可能并未深入了解。接下来&#xff0c;我们将深入挖掘真人…
阅读更多...
等保测评二级有哪些标准

等保测评二级有哪些标准

等级保护测评&#xff08;等保测评&#xff09;是中国的一项网络安全标准&#xff0c;旨在评估和确保关键信息基础设施的安全。二级等保测评是适用于一般级别的信息系统&#xff0c;这些系统一旦受损&#xff0c;可能会对社会秩序、公共利益和公民权利造成一定程度的影响。 二级…
阅读更多...
快速输出标准化3D课件，打造沉浸式培训体验

快速输出标准化3D课件，打造沉浸式培训体验

随着技术的日新月异和市场的迅猛扩张&#xff0c;企业对员工专业技能培训的需求日益凸显。传统的培训方式往往依赖于实地操作、现场指导&#xff0c;这不仅需要大量的人力、物力和时间成本&#xff0c;而且存在安全风险。特别是化工、机械制造等行业&#xff0c;实操培训的成本…
阅读更多...
浅析扩散模型与图像生成【应用篇】(二十二)——DreamBooth

浅析扩散模型与图像生成【应用篇】(二十二)——DreamBooth

21. DreamBooth: Fine Tuning Text-to-Image Diffusion Models for Subject-Driven Generation 本文提出一种根据少量样例图片来对文生图模型进行微调的方法&#xff0c;从而可以生成包含样例物体&#xff0c;但风格、姿态、背景都可以任意修改的图片。现有的文生图模型都是需要…
阅读更多...
智能可编程脉冲电源：为电源行业带来前所未有的创新

智能可编程脉冲电源：为电源行业带来前所未有的创新

智能可编程脉冲电源是一种具有高精度、高可靠性、节能降耗和可编程性强等特点的电源设备。它主要由脉冲发生器、功率调节电路和控制电路等组成。脉冲发生器产生的脉冲信号可以驱动功率调节电路&#xff0c;实现对电源输出的电压和电流的精确控制。通过控制电路对脉冲信号进行调…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站