给公司做网站 图片倾权,绵阳市住房和城乡建设局网站,wordpress用什么主题,简单网页制作模板代码#x1f3a5; 个人主页#xff1a;Dikz12#x1f525;个人专栏#xff1a;算法(Java)#x1f4d5;格言#xff1a;吾愚多不敏#xff0c;而愿加学欢迎大家#x1f44d;点赞✍评论⭐收藏
目录
1. 计算布尔二叉树的值 1.1 题目描述
1.2 题解
1.3 代码实现 2. 求根节… 个人主页Dikz12个人专栏算法(Java)格言吾愚多不敏而愿加学欢迎大家点赞✍评论⭐收藏
目录
1. 计算布尔二叉树的值 1.1 题目描述
1.2 题解
1.3 代码实现 2. 求根节点到叶子节点数字之和 2.1 题目描述
2.2 题解 2.3 代码实现
3. 二叉树剪枝
3.1 题目描述
3.2 题解
3.3 代码实现
4. 验证二叉搜索树
4.1 题目描述 4.2 题解
4.3 代码实现 5.二叉搜索树中第k个小的元素 5.1 题目描述
5.2 题解
5.3 代码实现 6. 二叉树的所有路径
6.1 题目描述
6.2 题解
6.3 代码实现 1. 计算布尔二叉树的值 1.1 题目描述 1.2 题解 递归函数设计boolean evaluateTree(TreeNode root) 返回值当前节点值 参数当前节点指针。 函数作⽤求得当前节点通过逻辑运算符得出的值。 递归函数流程 当前问题规模为 n1 时即叶⼦节点直接返回当前节点值 递归求得左右⼦节点的值 通过判断当前节点的逻辑运算符计算左右⼦节点值运算得出的结果
1.3 代码实现 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.1 题目描述 2.2 题解 算法思路 在前序遍历的过程中我们可以往左右⼦树传递信息并且在回溯时得到左右⼦树的返回值。递归函 数可以帮我们完成两件事 将⽗节点的数字与当前节点的信息整合到⼀起计算出当前节点的数字然后传递到下⼀层进⾏递 归 当遇到叶⼦节点的时候就不再向下传递信息⽽是将整合的结果向上⼀直回溯到根节点。 在递归结束时根节点需要返回的值也就被更新为了整棵树的数字和。 2.3 代码实现 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 num 0;if(root.left ! null) {num dfs(root.left,preSum);}if(root.right ! null) {num dfs(root.right,preSum);}return num;}
3. 二叉树剪枝
3.1 题目描述 3.2 题解 算法流程 递归函数设计void dfs(TreeNode root) 返回值⽆ 参数 当前需要处理的节点 函数作⽤判断当前节点是否需要删除若需要删除则删除当前节点。 后序遍历的主要流程 递归出⼝当传⼊节点为空时不做任何处理 递归处理左⼦树 递归处理右⼦树 处理当前节点判断该节点是否为叶⼦节点即左右⼦节点均被删除当前节点成为叶⼦节点 并且节点的值为 0 a. 如果是就删除掉 b. 如果不是就不做任何处理。
3.3 代码实现 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) {root null;}return root;}
4. 验证二叉搜索树
4.1 题目描述 4.2 题解 算法思路 如果⼀棵树是⼆叉搜索树那么它的中序遍历的结果⼀定是⼀个严格递增的序列。 因此我们可以初始化⼀个⽆穷⼩的全区变量⽤来记录中序遍历过程中的前驱结点。那么就可以在 中序遍历的过程中先判断是否和前驱结点构成递增序列然后修改前驱结点为当前结点传⼊下⼀ 层的递归中。 4.3 代码实现 long prev Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root null) {return true;}boolean left isValidBST(root.left);//剪枝if(left false) {return false;}//当前节点boolean ret false;if(prev root.val) {prev root.val;ret true; }boolean right isValidBST(root.right);return left ret right;} 5.二叉搜索树中第k个小的元素 5.1 题目描述 5.2 题解 算法思路 上述解法不仅使⽤⼤量额外空间存储数据并且会将所有的结点都遍历⼀遍。 但是我们可以根据中序遍历的过程只需扫描前 k 个结点即可。 因此我们可以创建⼀个全局的计数器 count将其初始化为 k每遍历⼀个节点就将 count--。直到 某次递归的时候count 的值等于 0说明此时的结点就是我们要找的结果。 5.3 代码实现 int count;int ret;public int kthSmallest(TreeNode root, int k) {count k;dfs(root);return ret;}public void dfs(TreeNode root) {if(root null) {return;}dfs(root.left);count--;if(count 0) {ret root.val;return;}dfs(root.right);} 6. 二叉树的所有路径
6.1 题目描述 6.2 题解 算法思路 使⽤深度优先遍历DFS求解。 路径以字符串形式存储从根节点开始遍历每次遍历时将当前节点的值加⼊到路径中如果该节点 为叶⼦节点将路径存储到结果中。否则将 - 加⼊到路径中并递归遍历该节点的左右⼦树。 定义⼀个结果数组进⾏递归。递归具体实现⽅法如下 如果当前节点不为空就将当前节点的值加⼊路径 path 中否则直接返回 判断当前节点是否为叶⼦节点如果是则将当前路径加⼊到所有路径的存储数组 ret 中 否则将当前节点值加上 - 作为路径的分隔符继续递归遍历当前节点的左右⼦节点。 返回结果数组。
6.3 代码实现 ListString ret;public ListString binaryTreePaths(TreeNode root) {ret new ArrayList();dfs(root, new StringBuffer());return ret;}public void dfs(TreeNode root, StringBuffer _path) {StringBuffer path new StringBuffer(_path);path.append(Integer.toString(root.val));if (root.left null root.right null) {ret.add(path.toString());return;}path.append(-);if (root.left ! null) {dfs(root.left, path);}if (root.right ! null)dfs(root.right, path);}
