1、DFS算法简介

DFS算法是在树或者图这样的数据结构中常用的一种遍历算法。

这个算法会尽可能深的搜索树或者图的分支直到⼀条路径上的所有节点都被遍历完毕然后再回溯到上一层继续寻找另外一条路遍历。

简单来说DFS就是优先考虑深度换句话说就是一条路走到黑直到无路可走的情况下才会选择回头然后重新选择一条路。

在二叉树中常见的深度优先遍历有前序遍历、中序遍历以及后序遍历。

2、算法实战应用【leetcode】

dfs(root)宏观思想--函数体返回左子树的布尔值返回右子树的布尔值根据当前根节点返回最终结果函数出口叶子节点根据叶子节点数值返回布尔类型值

2.1.2

evaluateTree(root.left);boolean

right

evaluateTree(root.right);return

root.val

递归的过程中我们需要传递上层以及本层节点数字之和preSum将上层以及本层节点数字之和preSum传递给当前根节点的左右子树返回左右子树数值之和函数出口叶子节点。

注意要先将叶子节点的数值注入总和之中再返回

2.2.2

思想后序遍历当根节点的左右子树的所有值均为0时才可删除当前树从叶子节点开始判断若其值为0则可删除可被删除的节点返回null父节点.left/right接收null修改其父节点的指向继续判断当前节点

2.3.2

pruneTree(root.left);root.right

pruneTree(root.right);if(root.left

null

Long.MIN_VALUE(记录上一个节点的值)中序遍历(将当前根节点依次和prev比较查看序列是否有序)需当前节点的左子树与右子树均满足二叉搜索树以及当前节点本身满足二叉搜索树才能说明该树为二叉搜索树若当前节点满足则更新prev的值为当前节点的val值若当前节点不满足则返回false再通过剪枝优化代码使函数提前终止并返回false。

2.4.2

ret中序遍历(通过有序序列查找目标值)因为中序遍历得到的是一个有序序列所以利用count计数计到第k个数时使用ret存入得到目标值后在通过剪枝优化函数使递归返回

2.5.2

return;dfs(root.left);count--;if(count

{ret

root.val;//剪枝return;}dfs(root.right);}

2.6

“恢复现场”注意本题不能使用全局变量path恢复现场因为本层路径的修改会影响到上一层。

解法使用局部变量(函数传参)path回溯到上一层时函数会自动“恢复现场”。

剪枝

优化代码

StringBuffer(path_);path.append(root.val);if(root.left

null

{ret.add(path.toString());return;}path.append(-);//if

剪枝省略函数出口if(root.left