DFS算法专题(一)——二叉树中的深搜【回溯与剪枝的初步注入】

目录

1、DFS算法简介

2、算法实战应用【leetcode】

2.1 计算布尔二叉树的值

2.1.1 算法原理 

2.1.2 算法代码

2.2 求根节点到叶节点数字之和 

 2.2.1 算法原理

​2.2.2 算法代码

2.3 二叉树剪枝

2.3.1 算法原理

2.3.2 算法代码

2.4 验证二叉搜索树 

2.4.1 算法原理 

2.4.2 算法代码

2.5 二叉搜索树中第K小的元素 

2.5.1 算法原理

2.5.2 算法代码

2.6 二叉树的所有路径 

2.6.1 算法原理

​2.6.2 算法代码

---

1、DFS算法简介

DFS，全称为 Depth First Traversal，深度优先遍历。

DFS算法是在树或者图这样的数据结构中常用的一种遍历算法。这个算法会尽可能深的搜索树或者图的分支，直到⼀条路径上的所有节点都被遍历完毕，然后再回溯到上一层，继续寻找另外一条路遍历。

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

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

2、算法实战应用【leetcode】

2.1 计算布尔二叉树的值

. - 力扣（LeetCode）

2.1.1 算法原理 

1. 以宏观角度看待递归
2. 后序遍历拿到最终值
3. 函数头：boolean dfs(root)；
4. 宏观思想-->函数体：返回左子树的布尔值，返回右子树的布尔值，根据当前根节点返回最终结果
5. 函数出口：叶子节点，根据叶子节点数值返回布尔类型值

2.1.2 算法代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean evaluateTree(TreeNode root) {if(root.left == null) return root.val == 0 ? false : true;boolean left = evaluateTree(root.left);boolean right = evaluateTree(root.right);return root.val == 2 ? left || right : left && right;}
}

---

2.2 求根节点到叶节点数字之和 

 . - 力扣（LeetCode）

 2.2.1 算法原理

1. 递归的过程中，我们需要传递上层以及本层节点数字之和preSum
2. 将上层以及本层节点数字之和preSum传递给当前根节点的左右子树
3. 返回左右子树数值之和
4. 函数出口：叶子节点。注意：要先将叶子节点的数值注入总和之中再返回

2.2.2 算法代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int sumNumbers(TreeNode root) {return dfs(root, 0);}public int dfs(TreeNode root, int preSum) {preSum = preSum * 10 + root.val;if(root.left == null && root.right == null) return preSum;int ret = 0;//剪枝if(root.left != null) ret += dfs(root.left, preSum);if(root.right != null) ret += dfs(root.right, preSum);return ret;}
}

---

2.3 二叉树剪枝

. - 力扣（LeetCode）

2.3.1 算法原理

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

2.3.2 算法代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode pruneTree(TreeNode root) {if(root == null) return null;root.left = pruneTree(root.left);root.right = pruneTree(root.right);if(root.left == null && root.right == null && root.val == 0) return null;else return root;}
}

---

2.4 验证二叉搜索树 

. - 力扣（LeetCode）

2.4.1 算法原理 

本题所用思想： 

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

 

2.4.2 算法代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null) return true;boolean left = isValidBST(root.left);if(prev >= root.val) {return false;}prev = root.val;boolean right = isValidBST(root.right);return left && right;}
}

---

2.5 二叉搜索树中第K小的元素 

. - 力扣（LeetCode）

2.5.1 算法原理

 与上一题思想一致，因为是二叉搜索树，所以中序遍历是突破口： 

1. 设置两个全局变量：public int count+public int ret
2. 中序遍历(通过有序序列查找目标值)
3. 因为中序遍历得到的是一个有序序列，所以利用count计数，计到第k个数时，使用ret存入
4. 得到目标值后，在通过剪枝优化函数，使递归返回

2.5.2 算法代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int count;public int ret;public int kthSmallest(TreeNode root, int k) {count = k;dfs(root);return ret;}public void dfs(TreeNode root) {//count == 0 -> 剪枝if(root == null || count == 0) return;dfs(root.left);count--;if(count == 0) {ret = root.val;//剪枝return;}dfs(root.right);}
}

---

2.6 二叉树的所有路径 

. - 力扣（LeetCode）

2.6.1 算法原理

本题使用思想： 

1. 设置全局变量：List<String> ret;
2. 回溯 -> “恢复现场”
3. 注意：本题不能使用全局变量path恢复现场，因为本层路径的修改会影响到上一层。解法：使用局部变量(函数传参)path，回溯到上一层时，函数会自动“恢复现场”。
4. 剪枝 -> 优化代码

函数设计：

• 函数头：void dfs(root,path);
• 函数体：非叶子：root.val+"->" ；叶子：root.val + ret.add(path) + return(剪枝)
• 函数出口 -> 剪枝处理

2.6.2 算法代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<String> ret = new ArrayList<>();public List<String> binaryTreePaths(TreeNode root) {//path -> 记录路径//回溯 -> 函数自动“恢复现场”dfs(root, new StringBuffer());return ret;}public void dfs(TreeNode root, StringBuffer path_) {//保留上一层路径StringBuffer path = new StringBuffer(path_);path.append(root.val);if(root.left == null && root.right == null) {ret.add(path.toString());return;}path.append("->");//if -> 剪枝，省略函数出口if(root.left != null) dfs(root.left, path);if(root.right != null) dfs(root.right, path);}
}

---

END