青岛网站开发建设,校园网站系统的建设,个人网站免费域名和服务器,中国建设银行个人网上银行官方网站深度优先遍历#xff08;DFS#xff0c;全称为 Depth First Traversal#xff09;#xff0c;是我们树或者图这样的数据结构中常⽤的 ⼀种遍历算法。这个算法会尽可能深的搜索树或者图的分支#xff0c;直到⼀条路径上的所有节点都被遍历 完毕#xff0c;然后再回溯到上… 深度优先遍历DFS全称为 Depth First Traversal是我们树或者图这样的数据结构中常⽤的 ⼀种遍历算法。这个算法会尽可能深的搜索树或者图的分支直到⼀条路径上的所有节点都被遍历 完毕然后再回溯到上⼀层继续找⼀条路遍历。 在⼆叉树中常见的深度优先遍历为前序遍历、中序遍历以及后序遍历。 因为树的定义本⾝就是递归定义因此采⽤递归的方法去实现树的三种遍历不仅容易理解⽽且代码很简洁。并且前中后序三种遍历的唯⼀区别就是访问根节点的时机不同在做题的时候选择⼀个适当的遍历顺序对于算法的理解是非常有帮助的。 一、计算布尔二叉树的值
1.题目描述 2.算法思路
书面解释就是 1. 对于规模为 n 的问题需要求得当前节点值。 2. 节点值不为 0 或 1 时规模为 n 的问题可以被拆分为规模为 n-1 的子问题 a. 所有子节点的值 b. 通过子节点的值运算出当前节点值。 3. 当问题的规模变为 n1 时即叶⼦节点的值为 0 或 1我们可以直接获取当前节点值为 0 或 1。 画图来理解一下 我们如果想知道根节点true or false我们需要知道其子节点true or false进而层层递归 3.代码实现
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;}
};二、求根节点到叶节点数字之和
1.题目描述 2.算法思路 通过前序遍历往左右子树传递信息并且在回溯时得到左右子树的返回值。让递归函数完成两件事 1. 将父节点的数字与当前节点的信息整合到⼀起计算出当前节点的数字然后传递到下⼀层进行递归 2. 当遇到叶子节点的时候就不再向下传递信息将整合的结果向上⼀直回溯到根节点。 在递归结束时根节点需要返回的值也就被更新为了整棵树的数字和。 递归函数设计int dfs(TreeNode* root, int num) 1. 返回值当前子树计算的结果数字和 2. 参数 num递归过程中往下传递的信息父节点的数字 3. 函数作用整合父节点的信息与当前节点的信息计算当前节点数字并向下传递再回溯时返回当前子树当前节点作为子树根节点数字和。 我们画图来理解一下,举个例子: 我们有如下二叉树 首先,我们 合父节点的信息与当前节点的信息计算当前节点数字并向下传递: 溯时返回当前子树当前节点作为子树根节点数字和: 最后返回计算的和就行了 递归函数流程 1. 当遇到空节点的时候说明这条路从根节点开始没有分⽀返回 0 2. 结合⽗节点传下的信息以及当前节点的 val计算出当前节点数字 sum 3. 如果当前结点是叶子节点直接返回整合后的结果 sum 4. 如果当前结点不是叶父节点将 sum 传到左右子树中去得到左右子树中节点路径的数字和然 后相加后返回结果。 3.代码实现 class Solution {
public:int dfs(TreeNode* root, int prevSum) {if (root nullptr) {return 0;}int sum prevSum * 10 root-val;if (root-left nullptr root-right nullptr) {return sum;} else {return dfs(root-left, sum) dfs(root-right, sum);}}int sumNumbers(TreeNode* root) {return dfs(root, 0);}
}; 三、二叉树剪枝 1.题目描述
2.算法思路 如果我们选择从上往下删除我们需要收集左右⼦树的信息这可能导致代码编写相对困难。然而 通过观察我们可以发现如果我们先删除最底部的叶子节点然后再处理删除后的节点最终的结果并不会受到影响。 因此我们可以采⽤后序遍历的方式来解决这个问题。在后序遍历中我们先处理左子树然后处理 右子树最后再处理当前节点。在处理当前节点时我们可以判断其是否为叶子节点且其值是否为 0 如果满足条件我们可以删除当前节点。 • 需要注意的是在删除叶子节点时其父节点很可能会成为新的叶子节点。因此在处理完子节点后我们仍然需要处理当前节点。这也是为什么选择后序遍历的原因后序遍历⾸先遍历到的一定是叶子节点。 • 通过使用后序遍历我们可以逐步删除叶子节点并且保证删除后的节点仍然满足删除操作的要 求。这样我们可以较为方便地实现删除操作而不会影响最终的结果。 • 若在处 理结束后所有叶子节点的值均为 1则所有子树均包含 1此时可以返回。 算法流程 递归函数设计void dfs(TreeNode* root) 1. 返回值无 2. 参数 当前需要处理的节点 3. 函数作用判断当前节点是否需要删除若需要删除则删除当前节点。 后序遍历的主要流程 1. 递归出口当传入节点为空时不做任何处理 2. 递归处理左子树 3. 递归处理右子树 4. 处理当前节点判断该节点是否为叶⼦节点即左右⼦节点均被删除当前节点成为叶子节点 并且节点的值为 0 a. 如果是就删除掉 b. 如果不是就不做任何处理。 3.代码实现: 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 nullptr;}return root;}
}; 四、验证二叉搜索树 1.题目描述 2.算法思路 如果一棵树是二叉搜索树那么它的中序遍历的结果一定是⼀个严格递增的序列。 因此我们可以初始化⼀个无穷小的全区变量用来记录中序遍历过程中的前驱结点。那么就可以在中序遍历的过程中先判断是否和前驱结点构成递增序列然后修改前驱结点为当前结点传入下一层的递归中。 算法流程 初始化⼀个全局的变量 prev⽤来记录中序遍历过程中的前驱结点的 val 中序遍历的递归函数中 a. 设置递归出⼝root nullptr 的时候返回 true b. 先递归判断左⼦树是否是⼆叉搜索树⽤ retleft 标记 c. 然后判断当前结点是否满⾜⼆叉搜索树的性质用 retcur 标记 ▪ 如果当前结点的 val ⼤于 prev说明满足条件retcur 改为 true ▪ 如果当前结点的 val ⼩于等于 prev说明不满⾜条件retcur 改为 false d. 最后递归判断右⼦树是否是⼆叉搜索树⽤ retright 标记 只有当 retleft、 retcur 和 retright 都是 true 的时候才返回 true。 3.代码实现 class Solution
{
public:long prev LONG_MIN;bool isValidBST(TreeNode* root) {if(root nullptr) return true;bool left isValidBST(root-left);// 剪枝if(left false) return false;bool cur false;if(root-val prev)cur true;// 剪枝if(cur false) return false;prev root-val;bool right isValidBST(root-right);return left right cur;}
}; 感谢大家的观看如有错误欢迎指正
