青岛网站开发工资,张家港江阴网站制作,中国电力工程造价信息网,会员注册网站怎么做大佬们好呀#xff0c;这一次讲解的是二叉树的深度搜索#xff0c;大佬们请阅
1.前言
⼆叉树中的深搜#xff08;介绍#xff09;
深度优先遍历#xff08;DFS#xff0c;全称为DepthFirstTraversal#xff09;#xff0c;是我们树或者图这样的数据结构中常⽤的⼀种…大佬们好呀这一次讲解的是二叉树的深度搜索大佬们请阅
1.前言
⼆叉树中的深搜介绍
深度优先遍历DFS全称为DepthFirstTraversal是我们树或者图这样的数据结构中常⽤的⼀种***遍历算法***。这个算法会尽可能深的搜索树或者图的分⽀直到⼀条路径上的所有节点都被遍历完毕然后再回溯到上⼀层继续找⼀条路遍历。 在⼆叉树中常⻅的深度优先遍历为前序遍历、中序遍历以及后序遍历。 因为树的定义本⾝就是递归定义因此采⽤递归的⽅法去实现树的三种遍历不仅容易理解⽽且代码很简洁。并且前中后序三种遍历的唯⼀区别就是 ***访问根节点的时机不同***在做题的时候选择⼀个适当的遍历顺序对于算法的理解是⾮常有帮助的。
好了接下来让我们用习题来介绍吧
1.计算布尔⼆叉树的值medium
题目链接计算布尔二叉树的值 题目介绍
给你⼀棵完整⼆叉树的根这棵树有以下特征 叶⼦节点要么值为0要么值为1其中0表⽰False1表⽰True。 ⾮叶⼦节点要么值为2要么值为3其中2表⽰逻辑或OR3表⽰逻辑与AND。 计算⼀个节点的值⽅式如下 如果节点是个叶⼦节点那么节点的值为它本⾝即True或者False。 否则计算两个孩⼦的节点值然后将该节点的运算符对两个孩⼦值进⾏运算。 返回根节点root的布尔运算值。 完整⼆叉树是每个节点有0个或者2个孩⼦的⼆叉树。 叶⼦节点是没有孩⼦的节点。 算法思路 对于规模为n的问题需要求得当前节点值。 节点值不为0或1时, ***规模为n的问题可以被拆分为规模为n-1的⼦问题*** a所有⼦节点的值b通过⼦节点的值运算出当前节点值。 当问题的规模变为n1时即叶⼦节点的值为0或1我们可以直接获取当前节点值为0或1。
递归函数流程 当前问题规模为n1时即叶⼦节点直接返回当前节点值 递归求得左右⼦节点的值 通过***判断当前节点的逻辑运算符***计算左右⼦节点值运算得出的结果
代码如下
class Solution {
public:bool evaluateTree(TreeNode* root) {if(root-leftnullptr||root-rightnullptr){return root-val;}else{if(root-val2)return evaluateTree(root-left)||evaluateTree(root-right);elsereturn evaluateTree(root-left)evaluateTree(root-right);}}
};2. 求根节点到叶节点数字之和medium
题目链接求根节点到叶节点数字之和 题目介绍 给你⼀个⼆叉树的根节点root树中每个节点都存放有⼀个0到9之间的数字。 每条从根节点到叶节点的路径都代表⼀个数字 例如从根节点到叶节点的路径1-2-3表⽰数字123。 计算从根节点到叶节点⽣成的所有数字之和。 叶节点是指没有⼦节点的节点。 解题思路
解法dfs-前序遍历
前序遍历按照根节点、左⼦树、右⼦树的顺序遍历⼆叉树的所有节点通常⽤于 ⼦节点的状态依赖于⽗节点状态的题⽬。
在前序遍历的过程中我们可以 往左右⼦树传递信息并且在回溯时得到左右⼦树的返回值。递归函数可以帮我们完成两件事
将⽗节点的数字与当前节点的信息整合到⼀起计算出当前节点的数字然后传递到下⼀层进⾏递归当遇到叶⼦节点的时候就***不再向下传递信息***⽽是 ***将整合的结果向上⼀直回溯到根节点***。在递归结束时根节点需要返回的值也就被更新为了整棵树的数字和。
递归函数流程 当遇到空节点的时候说明这条路从根节点开始没有分⽀返回0 结合⽗节点传下的信息以及当前节点的val计算出当前节点数字sum 如果当前结点是叶⼦节点直接返回整合后的结果sum 如果当前结点不是叶⼦节点将sum传到左右⼦树中去得到左右⼦树中节点路径的数字和然后 ***相加后返回结果***。
代码如下
class Solution {
public:int sumNumbers(TreeNode* root) {return sumNumber(root,0);}int sumNumber(TreeNode* root,int x) {if(rootnullptr)return x;else{xx*10root-val;}if(root-left!nullptrroot-right!nullptr)return sumNumber(root-left,x)sumNumber(root-right,x);else if(root-left!nullptr)return sumNumber(root-left,x);else if(root-right!nullptr)return sumNumber(root-right,x);elsereturn x;}
};3.⼆叉树剪枝medium
题⽬链接二叉树剪枝
题目介绍
给你⼆叉树的根结点root此外树的每个结点的值要么是0要么是1。 返回移除了所有不包含1的⼦树的原⼆叉树。 节点node的⼦树为node本⾝加上所有node的后代。 解法dfs-后序遍历 后序遍历按照左⼦树、右⼦树、根节点的顺序遍历⼆叉树的所有节点通常⽤于 ⽗节点的状态依赖于⼦节点状态的题⽬。
后序遍历的主要流程 递归出⼝当传⼊节点为空时不做任何处理 递归处理***左⼦树*** 递归处理***右⼦树*** 处理当前节点判断该节点是否为叶⼦节点即左右⼦节点均被删除,前点成为叶⼦节点并且节点的值为0 a. 如果是就删除掉 b. 如果不是就不做任何处理。
代码如下
class Solution {
public:TreeNode* pruneTree(TreeNode* root) {dfs(root);if(root-leftnullptrroot-rightnullptrroot-val0)return nullptr;elsereturn root;}bool dfs(TreeNode* root) {if (root) {if(root-leftnullptrroot-rightnullptr)return root-val;bool l dfs(root-left);bool r dfs(root-right);if (l false) {root-left nullptr;}if (r false) {root-right nullptr;}if(root-val0)return l || r;elsereturn 1;}elsereturn false;}
};4. ⼆叉搜索树中第k⼩的元素medium
题目链接⼆叉搜索树中第k⼩的元素
题目描述 给定一个二叉搜索树的根节点 root 和一个整数 k 请你设计一个算法查找其中第 k 小的元素从 1 开始计数。 解题思路 中序遍历计数器剪枝 上述解法不仅使⽤⼤量额外空间存储数据并且会将所有的结点都遍历⼀遍。 但是我们可以根据中序遍历的过程只需扫描前k个结点即可。 因此我们可以创建⼀个全局的计数器***count***将其初始化为***k***每遍历⼀个节点就将***count–***。直到某次递归的时候count的值等于0说明此时的结点就是我们要找的结果。
代码如下
class Solution {
public:int kthSmallest(TreeNode* root, int k) {int flag 0;dfs(root, k, flag);return flag;}void dfs(TreeNode* root, int k, int flag) {if (root) {dfs(root-left, k, flag);k--;if (k 0) {flag root-val;}dfs(root-right, k, flag);}}
};好啦递归问题就讲到这里下一次讲解的是搜索回溯和全排列我们下次再见
