算法沉淀 —— 深度搜索(dfs)

这篇具有很好参考价值的文章主要介绍了算法沉淀 —— 深度搜索(dfs)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、计算布尔二叉树的值

【题目链接】:2331. 计算布尔二叉树的值
【题目】:
算法沉淀 —— 深度搜索(dfs),算法指南,算法,深度优先,递归,leetcode,学习和成长

【分析】:
 在确定一颗二叉树的布尔值前,我们需要先得到左子树、右子树的结果(0/1)。如果左子树、右子树不是叶子节点,显然这是一个递归子问题(将求左子树、右子树的布尔值);
 最后就是根据root的值来判断对左/右子树结果的操作(如果是2,按位或;否则为按位与)

【代码实现】:

class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if(root->left == nullptr && root->right == nullptr)
            return root->val;
        //完成二叉树保证如果非叶子节点,则左右子树都不为空
        bool ansL = evaluateTree(root->left);//递归处理左子树
        bool ansR = evaluateTree(root->right);//递归处理右子树
        return root->val == 2 ? ansL | ansR : ansL & ansR;
    }
};

二、求根节点到叶节点数字之和

【题目链接】:129. 求根节点到叶节点数字之和

【题目】:
算法沉淀 —— 深度搜索(dfs),算法指南,算法,深度优先,递归,leetcode,学习和成长

【分析】:
 根节点到叶节点数字之和,显然如果当前节点为叶子节点,此时直接返回结果;否则需要得到当前路径之前路径和(假设为prev),此时当前路径数字和为root->val + prev*10。此时在重复上述过程,如果时叶子节点,直接返回结果;否则转化为递归子问题求解(左子树、右子树只有非空,都有结果)
由于根节点到叶节点的路径可能存在多条,每一条路径都存在一个结果。所以这里我们可以定义一个全局变量来记录最后的累计结果(具体看代码)
【代码实现】:

class Solution {
public:
    int sum = 0;
    int sumNumbers(TreeNode* root) {
        int prev = 0;
        _sumNumbers(root, 0);//prev用于记录当前节点前的路径和
        return sum;
    }

    void _sumNumbers(TreeNode* root, int prev)
    {
        prev = prev * 10 + root->val;//还是使用prev来保存当前路径数字和
        if(root->left)//左子树非空,必然存在结果,转化成递归子问题求解
           _sumNumbers(root->left, prev);
        if(root->right)//右子树非空,同上
           _sumNumbers(root->right, prev);
        if(root->left == nullptr && root->right == nullptr)//叶子节点, 累加当前路径和
            sum += prev;
    }
};

三、二叉树剪枝

【题目链接】:814. 二叉树剪枝
【题目】:
算法沉淀 —— 深度搜索(dfs),算法指南,算法,深度优先,递归,leetcode,学习和成长
算法沉淀 —— 深度搜索(dfs),算法指南,算法,深度优先,递归,leetcode,学习和成长
【分析】:
 本题中,我们可以采用二叉树后序遍历的思想。先对左子树、右子树分别进行剪枝操作。此时左/右子树中有两种结果:非空、非空(此时子树已经进行了剪枝)。所以此时当前节点必须满足左/右子树均为空,并且根节点为0时,才可继续剪枝。
【代码实现】:

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        //二叉树后序遍历,进行剪枝
        //对左/右子树剪枝后,左/右子树只有两种结果: 为空、剪完枝非空。
        if(root == nullptr)
            return nullptr;
        root->left = pruneTree(root->left);//对左子树剪枝
        root->right = pruneTree(root->right);//右子树剪枝
        if(root->left == nullptr && root->right == nullptr && root->val == 0)
        {
            delete root;//笔试建议省略此步,原因在于如果root不是new出来的,会报错
            root = nullptr;
        }
        return root;
    }
};

四、验证二叉搜索树

【题目链接】:98. 验证二叉搜索树
【题目】:
算法沉淀 —— 深度搜索(dfs),算法指南,算法,深度优先,递归,leetcode,学习和成长
算法沉淀 —— 深度搜索(dfs),算法指南,算法,深度优先,递归,leetcode,学习和成长

【分析】:
 我们可以利用二叉搜索树中序遍历是升序的性质来判断是否为二叉搜索树。但如何利用呢?
 其中一种思路是先用一个数组记录二叉树中序遍历结果,在判断是否为升序。但此时算法的空间复杂度为O(n)。
 另一种思路就是使用一个全局遍历(prev)来记录中序遍历的前一个数据,然后转化成当前节点和prev比较(当然还有prev值更新啦)。让后根据左子树、右子树、根节点的结果来判断是否符合AVL树(具体参考代码)
tips:

  • prev的初始值需要设置为LLONG_MIN(比INT_MIN小即可)。
    【代码实现】:
class Solution {
public:
    long long prev = LLONG_MIN;//保存中序遍历的前一个节点值
    bool isValidBST(TreeNode* root) {
        if(root == nullptr)
            return true;
        bool Left = isValidBST(root->left);//记录左子树结果
        bool cur = false;//记录当前根节点和上一个数据是否符合AVL树性质
        if(root->val > prev)
        {
            prev = root->val;
            cur = true;
        }
        bool Right = isValidBST(root->right);//记录左子树结果
        return Left && Right && cur;
        
    }
};

五、二叉搜索树中第K小的元素

【题目链接】:230. 二叉搜索树中第K小的元素
【题目】:
算法沉淀 —— 深度搜索(dfs),算法指南,算法,深度优先,递归,leetcode,学习和成长

算法沉淀 —— 深度搜索(dfs),算法指南,算法,深度优先,递归,leetcode,学习和成长
【分析】:
 本题意思非常明确,求第k小元素。我们可以通过中序遍历,每遍历一次元素,k–。直到k为1时,返回结果。
 这里博主推荐将返回值(定义为ret)、和k的值都设置为全局变量。然后和中序遍历一样,我们只需当k的值为1时,返回结果结果;并且每次遍历k–。
【代码实现】:文章来源地址https://www.toymoban.com/news/detail-851441.html

class Solution {
public:
    int count = 0, ret = 0;
    int kthSmallest(TreeNode* root, int k) {
        count = k;
        _kthSmallest(root);
        return ret;
    }

    void _kthSmallest(TreeNode* root)
    {
        if(root == nullptr || count == 0)
            return;
        _kthSmallest(root->left);
        if(--count == 0)
            ret = root->val;
        _kthSmallest(root->right);
    }
};

到了这里,关于算法沉淀 —— 深度搜索(dfs)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 深度优先搜索(DFS)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法,总是以“深度”作为前进的。实现方式是有很多,最

    2024年02月08日
    浏览(50)
  • [算法日志]图论: 深度优先搜索(DFS)

    ​ 深度优先搜索算法是一种遍历图这种数据结构的算法策略,其中心思想是朝图节点的一个方向不断跳转,当该节点无下一个节点或所有方向都遍历完时,便回溯朝上一个节点的另一个方向继续遍历。这种搜索策略与回溯法有异曲同工之妙。 正因为和回溯法有相似之处,所

    2024年02月03日
    浏览(62)
  • 【算法详解 | DFS算法】深度优先搜索解走迷宫问题 | 深度优先图遍历

    by.Qin3Yu 本文需要读者掌握 结构体 和 栈 的操作基础,完整代码将在文章末尾展示。 特别声明:本文为了尽可能使用简单描述,以求简单明了,可能部分专有名词定义不准确。 栈相关操作可以参考我的往期博文: 【C++数据结构 | 栈速通】使用栈完成十进制数转二四八进制数

    2024年02月03日
    浏览(49)
  • 第一周算法训练(dfs)(深度优先搜索算法)

    dfs: 深度优先搜索算法 ,是一种用于遍历或 搜索树或图的算法 .沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被

    2024年02月20日
    浏览(49)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)两种算法c++

    深度优先搜索(DFS)和广度优先搜索(BFS)是一种用于遍历或搜索树图的一种算法,在这个过程中保证图或数的每个结点被访问且仅被访问一次,再按照每个结点访问的顺序不同分为深搜和广搜。 本文只讨论这两种算法在搜索方面的应用! 深度优先搜索 ( Depth-First-Search,DFS )它 沿

    2024年02月13日
    浏览(47)
  • Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

    深度优先搜索( DFS )和广度优先搜索( BFS )是两种常用的图遍历算法,用于在图中搜索目标节点或遍历图的所有节点。本篇博客将介绍 DFS 和 BFS 算法的基本概念,并通过实例代码演示它们的应用。 😃😄 ❤️ ❤️ ❤️ 深度优先搜索( DFS )是一种用于遍历或搜索图或树

    2024年02月07日
    浏览(65)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(46)
  • 【数据结构与算法】搜索算法(深度优先搜索 DFS和广度优先搜索 BFS)以及典型算法例题

    【数据结构与算法】系列文章链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 【数据结构与算法】系列文章链接: 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题 【数据结构与算法】系列文章链

    2024年04月13日
    浏览(63)
  • 如何实现一个简单的深度优先搜索(DFS)算法?

    前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发者,这里都将为你提供一

    2024年02月07日
    浏览(53)
  • 【Python搜索算法】深度优先搜索(DFS)算法原理详解与应用,示例+代码

    目录 1 基本原理 2 DFS算法流程 3 时间复杂度 4 空间复杂度 5 DFS算法应用案例: 5.1 解决路径查找问题  5.2 解决图的连通性问题 5.3  拓扑排序 5.4  在树结构中进行深度遍历 深度优先搜索(DFS)是一种重要的图遍历算法,用于探索图中的节点和边。 DFS 是一种递归或栈(堆栈)

    2024年02月06日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包