怎样做免费网站卖东西,美容产品网站建设多少钱,淘宝天猫网上购物商城,网站地区词优化文章目录 了解DFS1.计算布尔二叉树的值思路代码展示 2.求根节点到叶节点数字之和思路代码展示 3.二叉树剪枝思路代码展示 4.验证二叉搜索树思路分析代码展示 5.二叉搜索树中第k小元素思路#xff1a;代码展示 6.二叉树的所有路径思路分析代码展示 总结 了解DFS
所谓DFS就是就… 文章目录 了解DFS1.计算布尔二叉树的值思路代码展示 2.求根节点到叶节点数字之和思路代码展示 3.二叉树剪枝思路代码展示 4.验证二叉搜索树思路分析代码展示 5.二叉搜索树中第k小元素思路代码展示 6.二叉树的所有路径思路分析代码展示 总结 了解DFS
所谓DFS就是就是深度优先搜索首先我们回到我们以前学习过的二叉树对于二叉树我们讲过深度优先遍历也就前序后序中序这三种遍历方式对于深度优先搜索深度优先遍历是一个过程在这个过程中我们加上搜索。 在一颗二叉树上对于遍历来说我们会一条路走到黑直到走到空的节点为止才会返回上一个节点走另一个分支但是对于DFS深度优先搜索来说我们的目的是、搜索当中的值而不是一味地遍历。 接下来我们通过几道题来深入理解这个算法
1.计算布尔二叉树的值 首先我们来理解题意题意很简单就是在一颗二叉树中只有0123这几个值他们分别代表的是false true || 我们来看看实际的一颗树 右边这颗二叉树就可以投影成左边这颗树的样子。
接下来我们来分析一下这个道题应该怎么做
思路
首先这道题说了这颗树是完整的二叉树意思就是所有节点要么一个节点都没有要么就是有两个节点。我们再来看这颗树的特征非叶子节点肯定是2或者3叶子节点肯定是1或者0所以这里划分就出来了我们对叶子节点和非叶子节点做不同的处理如果是叶子节点就直接返回当前节点的值如果不是叶子节点就判断一下该节点的值如果是2就对左子树和右子树进行||操作反之则进行操作即可。
函数头 函数头bool dfs(root) 函数体 遇到叶子节点返回叶子节点的值遇到非叶子节点对左子树和右子树进行递归操作。 递归出口 就是返回叶子节点的值
代码展示
class Solution {
public:bool evaluateTree(TreeNode* root) {//只用判断一边就可以if(root-rightnullptr){//叶子节点直接返回值return root-val;}//得到左子树的结果bool leftevaluateTree(root-left);//得到右子树的结果bool rightevaluateTree(root-right);//判断一下当前节点的值是2还是3进行操作还是||操作return root-val2?left||right:leftright;}
};2.求根节点到叶节点数字之和 题目解释 首先我们先给出一棵树 对于这棵树并不是说所有节点的和就是把所有节点的值加起来而是我们先看第一个路径4--9--5对于这个路径来说这个路径下对应的和就是495第二个路对应的是491第三个路径对应的是40. 从下面图应该可以看出
思路
对于这道题我们先来走一遍当我们进入根节点4的时候我们先递归左子树我们肯定必须要知道前面的和是多少因为我们要计算下一个节点的和所以必须知道前面节点的和是多少所以这里我们传递的参数就多了一个presum前驱和
函数头 函数头int dfs(root,presum) 因为这道题要求返回所有路径的和所以有一个返回值就是int
函数体 这里我们来想一下函数体是什么 我们把presum传进行当进入根节点的时候肯定不能带值因为根节点的前驱和是0所以这里我们传参的话传presum进去先是0进了函数之后我们先更新一下这个 presumpresumpresum*10root-val,更新了presum之后判断一下这个节点是否是叶子节点如果是叶子节点直接返回presum因为如果是叶子节点的话就说明这个路径的和已经求完了只需要求下一个路径的和就可以了这里我们用一个ret来存放一下左子树和右子树的和如果左子树不为空则返回将左子树的和加在ret上如果右子树不为空则再将右子树的和加在ret上最后返回ret。
代码展示
class Solution {
public:int dfs(TreeNode*root,int presum){//先将前驱和加上个presumpresum*10root-val;//如果是末尾节点的话直接返回前驱和if(root-leftnullptrroot-rightnullptr){return presum;}int ret0;//如果左节点不为空的话直接ret叠加上左节点的dfsif(root-left!nullptr){retdfs(root-left,presum);}//如果右节点不为空的话只额吉ret叠加右节点的dfsif(root-right!nullptr){retdfs(root-right,presum);}//返回两边树的总和return ret;}int sumNumbers(TreeNode* root) {return dfs(root,0);//刚传递进去的时候前驱和是0}
};3.二叉树剪枝 首先我们来看看下面一颗二叉树注意这颗二叉树上只有1或者0. 根据题目的意思就是将只含有0的子树删除对于上面这颗二叉树来说只含有0的子树首先我们看左子树左子树全是零直接删除再看右子树右子树的第一个节点是1不满足不能删除右子树的左子树的节点只有0直接删除右子树右子树只有1不能删除所以删除之后的二叉树就变成了下面的样子
思路
对于这道题我们要删除节点的话肯定要知道左子树和右子树的信息才能删除这个节点由于这个特殊的性质我们首先想到的则是后序遍历因为只有后序遍历才能将左子树和右子树的信息传递给节点确定了该如何遍历之后我们来讨论应该如何删除节点首先我们肯定不能从非叶子节点开始删因为我们根本不知道他的左子树和右子树的信息所以应该从叶子节点开始删所以这里删除的标志就是判断叶子节点的值是否为0如果为0则返回nullptr证明将这个节点删除了nullptr就是将删除的信息带给非叶子节点如果叶子节点不是0则返回当前节点如果返回的是非空节点这个信息的话就表示它的子树不是0
函数头 函数头dfs(root) 函数体 就是上面所讲的 递归出口 当遇到空节点的时候直接返回空节点。
代码展示
class Solution {
public:TreeNode* pruneTree(TreeNode* root) {//空节点直接返回if(rootnullptr){return nullptr;}//递归左子树root-leftpruneTree(root-left);//递归右子树root-rightpruneTree(root-right);//判断叶子节点的值if(root-leftnullptrroot-rightnullptrroot-val0){//delete root防止内存泄露return nullptr;}//如果是1则不删除else{return root;}}
};4.验证二叉搜索树 题目很简单就是验证一棵树是否是二叉搜索树如果是则直接返回true如果不是则返回false
思路分析
首先我们要知道一个二叉搜索树的一个很重要的性质就是它的中序遍历是一个有序序列这是一个这道题重要的突破口我们只需要记录它中序遍历的前驱的节点然后与当前节点进行比较即可如果比当前节点大则当前情况来看的话是二叉搜索树如果不满足的话直接返回false根本不需要进行判断了。注意当返回结果的时候我们要求左子树和右子树都满足还有根节点都满足二叉搜索树才是二叉搜索树否则不是二叉搜索树
函数头 函数头dfs(root) 函数体 在定义函数体的时候我们最好将prev(前驱定义为全局变量因为全局变量随着地递归不会改变我们只能手动改变 递归出口 当递归到空节点的时候直接返回true因为空节点就是二叉搜索树
代码展示
class Solution {long prevLONG_MIN;
public:bool isValidBST(TreeNode* root) {if(rootnullptr){return true;}bool leftisValidBST(root-left);//左子树都不满足则不用递归右子树了//剪枝if(leftfalse){return false;}//用cur表示当前节点是否满足bool curfalse;//如果满足则进入将cur置为trueif(root-valprev)curtrue;//不满足直接返回falseelsereturn false;//更新prevvprevroot-val;//递归右子树bool rightisValidBST(root-right);//返回左子树和右子树和当前节点是否满足是否是二叉搜索树return leftrightcur;}
};5.二叉搜索树中第k小元素 对于这道题还是和上一道题类似。
思路 对于上面这个二叉搜索树我们要求这个二叉搜索树的第k小的节点是不是应该用中序遍历因为中序遍历是有序的当我们中序遍历到叶子节点的时候我们就可以开始数了所以这里我们需要一个count来计数计算这个是第几小count我们最好选择全局变量因为全局变量不会随着递归而改变当我们中序遍历到叶子节点的时候我们的count就应该–操作每次–之后我么都应该判断一下这个count是否已经0了如果等于0我们用一个全局变量ret来接收一下这个值。
到3的时候直接用全局变量接收这个值。
代码展示
class Solution {int count;int ret;
public:int kthSmallest(TreeNode* root, int k) {countk;dfs(root);return ret;}void dfs(TreeNode*root){//count0是剪枝if(rootnullptr||count0)return;dfs(root-left);count--;if(count0){retroot-val;}dfs(root-right);}
};上面代码的递归出口的count0可不写因为我们也可以继续递归count为0只有一次所以如果count等于0我们可以直接不用递归了直接返回。
6.二叉树的所有路径 这道题需要返回的是一个路径的数组类型是string类的
思路分析
这道题要返回string类的数组的话为了不被递归影响到数组的值所以我们最好还是创建一个全局变量数组string的来记录这个每个路径还需要一个局部变量还需要一个string变量来记录当前路径。
函数头 函数头dfs(root,path) 传递一个局部变量的路径 函数体 注意函数体部分我们分析一下我们要求出所有路径我们先看看下面的输入和输出样例。 对于这个输出样例我们可以看到这个string不仅需要路径的值还需要一个-将其串联起来所以这里我们就分为了两种情况一种是非叶子节点一种是叶子节点对于非叶子节点我们不仅需要向string变量中加入当前值的字符还需要向里加入两个符号“-”但是对于叶子节点来说我们只需要向里添加当前节点对应值的字符就可以了注意添加完之后我们将string类的变量丢进string类的数组中注意这里我们不创建全局变量string的原因是因为当我们返回到上一节点的时候因为全局变量不会改变所以我们需要手动删除当前路径下的不需要的所有节点才能进入下一个分支就拿上面的图为例子当我们要进入右子树的时候我们必须将左子树中的2和3删完之后只留下1才能进入右子树分支但是对于局部变量则不一样注意这里我们创建局部变量的时候传参也要传拷贝构造而不是引用传引用的话和创建全局变量没有任何区别传递拷贝构造的话每次返回上一个分支都是一个新的string不会存在什么删除不需要的情况。
代码展示
class Solution {//全局若string数组用来存储字符串vectorstring ret;
public:vectorstring binaryTreePaths(TreeNode* root){//创建path记录路径string path;dfs(root,path);//返回字符数组return ret;}void dfs(TreeNode*root,string path){//叶子节点的处理方式if(root-leftnullptrroot-rightnullptr){pathto_string(root-val);ret.push_back(path);return;}//非叶子节点的处理方式pathto_string(root-val)-;//左子树不为空才递归为空直接剪枝if(root-left)dfs(root-left,path);//右子树也一样if(root-right)dfs(root-right,path);}
};总结
通过本文的探讨我们了解了深度优先搜索DFS在解决二叉树问题中的强大功能和广泛应用。DFS 通过其递归和迭代两种实现方式为我们提供了处理二叉树的不同策略使得问题的求解变得更加灵活。无论是前序遍历、中序遍历还是后序遍历DFS 都能够有效地遍历二叉树的每一个节点从而帮助我们解决各种实际问题如路径求和、树的对称性检查以及节点间距离计算等。
希望通过本文的介绍大家对 DFS 在二叉树问题中的应用有了更深入的理解并能够在实际编程中灵活运用这些技巧来解决复杂的树结构问题。感谢阅读期待在你们的代码中见到这些算法的身影如果有任何疑问或进一步的讨论欢迎在评论区留言我们一起交流学习。
