DFS:二叉树的深搜与回溯

这篇具有很好参考价值的文章主要介绍了DFS:二叉树的深搜与回溯。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

DFS:二叉树的深搜与回溯,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

   一、计算布尔二叉树的值

. - 力扣(LeetCode)

DFS:二叉树的深搜与回溯,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

class Solution {
public:
    bool evaluateTree(TreeNode* root) 
    {
      if(root->left==nullptr) return root->val==0?false:true; 
      bool left= evaluateTree(root->left);
      bool right=evaluateTree(root->right);
      return root->val==2?left||right:left&&right;
      //直接return root->val==2?evaluateTree(root->left)||evaluateTree(root->right):evaluateTree(root->left)&&evaluateTree(root->right)  会导致递归的时间变长,因为我们没有去记住返回值,所以一旦需要就得重新递归回去计算
    }
};

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

. - 力扣(LeetCode)

DFS:二叉树的深搜与回溯,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

class Solution {
public:
     int dfs(TreeNode* root,int presum)//presum也是为了回溯
     {
        if(root==nullptr) return 0;
        presum=10*presum+root->val;//因为不管怎么样都得加
        if(root->left==nullptr&&root->right==nullptr) return presum;
        //此时如果左右不为空,加上这个结果
         return dfs(root->left,presum)+dfs(root->right,presum);
     }
     int sumNumbers(TreeNode* root) 
    {  
        return dfs(root,0);
    }
};

三、二叉树剪枝

. - 力扣(LeetCode)

DFS:二叉树的深搜与回溯,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

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;
        return root;
    }
};

四、 验证二叉搜索树

 . - 力扣(LeetCode)

DFS:二叉树的深搜与回溯,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

class Solution {
public:
    long prev=LONG_MIN;//比负无穷还小
    bool isValidBST(TreeNode* root) 
    {
       if(root==nullptr) return true;//为空的话是符合条件的
      //进行中序遍历
      bool l=isValidBST(root->left);//先找左子树
      if(l==false) return false;//减枝(大多数的减枝就只是一个条件判断)
      bool temp=(prev<root->val);//判断当前是否大于前驱
      if(temp==false) return false;//减枝
      prev=root->val;//更新前驱
      bool r=isValidBST(root->right);//再找右子树
      return r;
    }
};

五、二叉搜索树中第k小的节点

. - 力扣(LeetCode)

DFS:二叉树的深搜与回溯,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

class Solution {
public:
    int count=0;
    int ret=0;
    int kthSmallest(TreeNode* root, int k) 
    {
      count=k;
      dfs(root);
      return ret;
    }
    void dfs(TreeNode* root)
    {
        if(root==nullptr) return;
        dfs(root->left);
        //中序遍历
        if(--count==0) {ret=root->val; return;}//if判断也是剪枝
        dfs(root->right);
    }
};

 六、二叉树的所有路径

DFS:二叉树的深搜与回溯,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

class Solution {
public:
    vector<string> ret;//利用全局变量来存储我们返回的结果
    void dfs(TreeNode* root,string path)
    {
      if(root==nullptr) return;//为空 啥也不干  
      path+=to_string(root->val);//不为空的话,把自己给加上
      if(root->left==nullptr&&root->right==nullptr) 
        ret.push_back(path); //如果是叶子节点,返回最终结果
      else //不是叶子节点的话,继续往后找
      {
        path+="->";
        //继续去左右子树去找
        dfs(root->left,path);
        dfs(root->right,path);
      }
    }
    vector<string> binaryTreePaths(TreeNode* root) 
    {
        dfs(root,"");
        return ret;
    }
};

 七、路径总和2

. - 力扣(LeetCode)

DFS:二叉树的深搜与回溯,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

思路1:全局path+回溯 

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) 
    {
       dfs(root,targetSum);
       return ret;
    }
    void dfs(TreeNode* root,int targetSum)
    {
        if(root==nullptr) return;
        //if(targetSum<0) return;有负数,所以不能剪枝
        targetSum-=root->val;
        path.push_back(root->val);
        if(root->left==nullptr&&root->right==nullptr&&targetSum==0) {ret.push_back(path);return;}
        dfs(root->left,targetSum);
        if(root->left)  path.pop_back();
        dfs(root->right,targetSum);
        if(root->right)  path.pop_back();
    }
};

思路2:形参path记录路径结果

class Solution {
public:
    vector<vector<int>> ret;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) 
    {
       dfs(root,targetSum,{});
       return ret;
    }
    void dfs(TreeNode* root,int targetSum,vector<int> path)
    {
        if(root==nullptr) return;
        targetSum-=root->val;
        path.push_back(root->val);
        if(root->left==nullptr&&root->right==nullptr&&targetSum==0) ret.push_back(path);
        dfs(root->left,targetSum,path);
        dfs(root->right,targetSum,path);
    }
};

八、从叶节点开始的最小字符串 

. - 力扣(LeetCode)

DFS:二叉树的深搜与回溯,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

思路1:全局path+回溯

class Solution {
public:
    string minpath;
    string path;
    string smallestFromLeaf(TreeNode* root) 
    {
        dfs(root);
       return minpath;
    }
    void dfs(TreeNode* root)
    {
        if(root==nullptr) return;
        //先加上对应的节点
        path=char(root->val+'a')+path;
        //如果是叶子节点,那么就和minpath进行比较,小的话更新
        if(root->left==nullptr&&root->right==nullptr)//是叶子,就要进行比较
        if(minpath.empty()||minpath>path) //为空的时候,也要更新
            minpath=path;//更新
        //没找到,就去左右子树找
        dfs(root->left);
        if(root->left) path.erase(path.begin());
        dfs(root->right);
        if(root->right) path.erase(path.begin());
    }
};

思路2:参数path记录路径结果 

class Solution {
public:
    string minpath;
    string smallestFromLeaf(TreeNode* root) 
    {
        dfs(root,"");
       return minpath;
    }
    void dfs(TreeNode* root,string path)
    {
        if(root==nullptr) return;
        //先加上对应的节点
        path=char(root->val+'a')+path;
        //如果是叶子节点,那么就和minpath进行比较,小的话更新
        if(root->left==nullptr&&root->right==nullptr)//是叶子,就要进行比较
        if(minpath.empty()||minpath>path) //为空的时候,也要更新
            minpath=path;//更新
        //没找到,就去左右子树找
        dfs(root->left,path);
        dfs(root->right,path);
    }
};

DFS:二叉树的深搜与回溯,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++文章来源地址https://www.toymoban.com/news/detail-853671.html

到了这里,关于DFS:二叉树的深搜与回溯的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • DFS:深搜+回溯+剪枝解决组合问题

                                                   创作不易,感谢支持!!! . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) 该题和前面是类似的,但是用回溯算法,会超

    2024年04月12日
    浏览(39)
  • 二叉树的遍历(递归法)

    递归的三要素: ①确定递归函数的参数和返回值 ②确定终止条件 ③确定单层递归的逻辑 以前序遍历为例: 1、确定递归函数的参数和返回值: 参数中需要传入list来存放节点的数值,除了这一点就不需要再处理什么数据了也不需要有返回值,因此递归函数的返回类型就是v

    2024年01月17日
    浏览(73)
  • DFS:深搜+回溯+剪枝解决排列、子集问题

                                        创作不易,感谢三连支持!!  . - 力扣(LeetCode) . - 力扣(LeetCode)  方案1:不合法就continue 方案2:合法才能进循环 . - 力扣(LeetCode) . - 力扣(LeetCode)  策略1:决策树以选不选作为参考,结果为叶子节点 策略2:决策树以选几个

    2024年04月16日
    浏览(66)
  • DFS:深搜+回溯+剪枝解决矩阵搜索问题

                                                   创作不易,感谢三连!!  . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) . - 力扣(LeetCode) 1、矩阵搜索问题经常要用到向量,也就是我们可以通过dx和dy来帮助我们定义方向

    2024年04月17日
    浏览(41)
  • ※【回溯】【深度优先前序】Leetcode 257. 二叉树的所有路径

    ---------------🎈🎈257. 二叉树的所有路径 题目链接🎈🎈------------------- 时间复杂度O(N) 空间复杂度O(N) 深度优先遍历 添加了 StringBulider 替代字符串拼接提升效率 toString() 转化为String .append() 添加元素 时间复杂度O(N) 空间复杂度O(N)

    2024年02月20日
    浏览(37)
  • 二叉树的非递归遍历算法

    二叉树的遍历是指访问二叉树的每个结点,且每个结点仅被访问一次。二叉树的遍历可按二叉树的构成以及访问结点的顺序分为4种方式:先序遍历、中序遍历、后序遍历和层次遍历。请至少给出其中一种遍历方式的非递归算法的思路和代码,并举例演示算法的执行过程。 算

    2023年04月24日
    浏览(41)
  • 二叉树BFS/DFS及重要递归接口--拿下二叉树--拿下数据结构--拿到好offer

     堆是一种特殊的二叉树(完全二叉树),由于有堆排序等实际的需求,堆是由类似顺序表的结构实现的,这是为了方便堆能够通过下标找到parent和child,进行比较大小以及交换等操作。 这里我们建立二叉树的每个结点,包含左右孩子指针left和right,还有存储的数据data。 然后

    2023年04月08日
    浏览(53)
  • 【LeetCode】105. 从前序与中序遍历序列构造二叉树,106. 从中序与后序遍历序列构造二叉树,144. 二叉树的前序遍历非递归实现,94. 二叉树的中序遍历非递归实现,145. 二叉树的后序

    给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的 先序遍历 , inorder 是同一棵树的 中序遍历 ,请构造二叉树并返回其根节点。 示例 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7] 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的

    2024年02月04日
    浏览(37)
  • 二叉树的遍历的递归与非递归算法

    按照一定规律对二叉树的 每个结点进行访问且 仅访问一次 ; 这里的访问:可以是计算二叉树中的结点数据,打印该结点的信息,也可以是对结点进行的任何其它操作! 为什么需要遍历二叉树? 从过遍历可以得到访问结点的顺序序列,遍历操作就是将二叉树的结点按一定的

    2024年04月15日
    浏览(37)
  • 二叉树的递归遍历与迭代遍历(图示)

    本文将讲述二叉树递归与迭代的相关知识。 🕺作者: 迷茫的启明星 专栏:【数据结构从0到1】 相关文章:《数据结构二叉树的链式存储讲解及前中后序遍历和层次遍历》 😘欢迎关注:👍点赞🙌收藏✍️留言 🏇 码字不易,你的👍点赞🙌收藏❤️关注对我真的很重要,有

    2024年02月04日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包