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 算法原理
- 以宏观角度看待递归
- 后序遍历拿到最终值
- 函数头：boolean dfs(root)；
- 宏观思想-->函数体：返回左子树的布尔值，返回右子树的布尔值，根据当前根节点返回最终结果
- 函数出口：叶子节点，根据叶子节点数值返回布尔类型值
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 算法原理
- 递归的过程中，我们需要传递上层以及本层节点数字之和preSum
- 将上层以及本层节点数字之和preSum传递给当前根节点的左右子树
- 返回左右子树数值之和
- 函数出口：叶子节点。注意：要先将叶子节点的数值注入总和之中再返回
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 算法原理
- 思想：后序遍历，当根节点的左右子树的所有值均为0时，才可删除当前树
- 从叶子节点开始判断，若其值为0则可删除
- 可被删除的节点返回null，父节点.left/right接收null，修改其父节点的指向
- 继续判断当前节点
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 算法原理
本题所用思想：
- 全局变量 int prev = Long.MIN_VALUE；(记录上一个节点的值)
- 中序遍历(将当前根节点依次和prev比较，查看序列是否有序)
- 需当前节点的左子树与右子树均满足二叉搜索树，以及当前节点本身满足二叉搜索树，才能说明该树为二叉搜索树
- 若当前节点满足，则更新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 算法原理
与上一题思想一致，因为是二叉搜索树，所以中序遍历是突破口：
- 设置两个全局变量：public int count+public int ret
- 中序遍历(通过有序序列查找目标值)
- 因为中序遍历得到的是一个有序序列，所以利用count计数，计到第k个数时，使用ret存入
- 得到目标值后，在通过剪枝优化函数，使递归返回
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 算法原理
本题使用思想：
- 设置全局变量：List<String> ret;
- 回溯 -> “恢复现场”
- 注意：本题不能使用全局变量path恢复现场，因为本层路径的修改会影响到上一层。解法：使用局部变量(函数传参)path，回溯到上一层时，函数会自动“恢复现场”。
- 剪枝 -> 优化代码
函数设计：
- 函数头：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