各国网站的域名,品牌建设的四条主线,台州百度关键词优化,哪里有网站开发目录
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 算法原理 …目录
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 countpublic 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 算法原理
本题使用思想
设置全局变量ListString 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 {ListString ret new ArrayList();public ListString 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
