vps用什么软件做网站,南宁网站设计多少钱,商城站时刻表,其它区便宜营销型网站建设#x1f495;什么样的灵魂就要什么样的养料#xff0c;越悲怆的时候我越想嬉皮。#x1f495; 作者#xff1a;Mylvzi 文章主要内容#xff1a;算法系列–递归(2) 前言:今天带来的是算法系列--递归(2)的讲解,包含六个和二叉树相关的题目哦 1.计算布尔⼆叉树的… 什么样的灵魂就要什么样的养料越悲怆的时候我越想嬉皮。 作者Mylvzi 文章主要内容算法系列–递归(2) 前言:今天带来的是算法系列--递归(2)的讲解,包含六个和二叉树相关的题目哦 1.计算布尔⼆叉树的值
链接: https://leetcode.cn/problems/evaluate-boolean-binary-tree/
分析:
函数头:传入节点,得到左右子树的值, boolean dfs(TreeNode root)函数体:dfs(root.left); dfs(root.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.求根节点到叶节点数字之和
链接: https://leetcode.cn/problems/sum-root-to-leaf-numbers/
分析:
代码:
class Solution {public int sumNumbers(TreeNode root) {return dfs(root,0);}private int dfs(TreeNode root, int presum) {// 1.计算当前节点的值presum presum * 10 root.val;// 递归出口if(root.left null root.right null) return presum;// 2.递归左子树int ret 0;if(root.left ! null) ret dfs(root.left,presum);// 3.递归右子树if(root.right ! null) ret dfs(root.right,presum);// 4.返回左右子树的总和return ret;}
}总结: 当一个递归函数不好想时,就去模拟一遍整个过程
比如本题,你要想想这个接口是干啥的,你想要这个接口帮你做什么–给接口一个根节点,你去给我算出左右子树的和,并且返回给我,那么就能确定出函数头;
返回值:int类型,左子树 右子树的和函数名:dfs参数:root,还要给我走到当前节点的值,我只有知道这个值,才能和子节点相连
3.⼆叉树剪枝
链接: https://leetcode.cn/problems/binary-tree-pruning/description/ 分析:
明确接口的作用:给你一个根节点root,你去给我判断左右子树是否满足剪枝的条件,如果满足就断开和根节点的连接,如果不满足继续保持连接即可函数头:返回值应该是TreeNode,当条件满足时,需要断开连接,直接返回null就可以实现,如果条件不满足,还是需要返回子根节点;函数名dfs,参数需要通过一个根节点就行函数体:先分别遍历左右子树,更新root的左右子树的连接条件,接着判断是否满足剪枝的条件,如果满足,返回null,表示需要剪枝,如果不满足,返回当前的根节点即可递归出口:当节点为空时,直接返回null
代码:
class Solution {public TreeNode pruneTree(TreeNode root) {return dfs(root);}private TreeNode dfs(TreeNode root) {if(root null) return null;// 递归出口root.left dfs(root.left);// 遍历左子树root.right dfs(root.right);// 遍历右子树if(root.left null root.right null root.val 0) // 条件满足将root置为空return null;else return root;}
}4. 验证⼆叉搜索树
链接: https://leetcode.cn/problems/validate-binary-search-tree/description/
分析:
本题要利用到二叉搜索树的一个性质–二叉搜索树的中序遍历的结果是一个有序序列
明确接口的作用:给你一个根节点,你去给我判断一下左右子树是否都符合二叉搜索树的条件,如果不满足直接返回false,满足返回true函数头:返回值是boolean,参数需要提供一个根节点,函数名是dfs函数体:由于要中序遍历,所以应该先遍历左子树,判断左子树是否满足二叉搜索树,如果不满足,直接返回false即可(此时就没有遍历根节点和右子树的必要了),如果满足,判断当前根节点的状态是否满足二叉搜索树,具体的判断条件就是比较root.val和prev值的大小,如果root.val prev,则不符合二叉搜索树的条件,直接返回false,如果root.val prev,则符合二叉搜索树的条件,继续判断右子树是否符合条件,如果右子树满足,返回true,如果不满足,返回false递归出口:当节点为空时,返回true 代码:
class Solution {// 二叉搜索树的性质:中序遍历的结果是一个有序的序列long prev Long.MIN_VALUE;// 设置为long是为了防止越界public boolean isValidBST(TreeNode root) {if(root null) return true;// 空树也是二叉搜索树boolean left isValidBST(root.left);if(left false) return false;// 剪枝boolean cur root.val prev ? true : false;if(cur false) return false;// 剪枝prev root.val;// 更新prevboolean right isValidBST(root.right);return right;}
}5.⼆叉搜索树中第 k ⼩的元素
链接: https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/
分析:
本题还是利用二叉搜索树的性质:二叉搜索树的中序遍历的结果是一个有序序列
设计一个ret作为返回值,设计一个cnt计数器,让cnt的初始值为k,通过中序遍历,每遍历到一个节点就让cnt--,当cnt 0是,将ret更新为cur.val,然后返回即可
代码:
class Solution {int cnt;int ret;public int kthSmallest(TreeNode root, int k) {cnt k;dfs(root);return ret;}private void dfs(TreeNode root) {if(root null || cnt 0) return;dfs(root.left);cnt--;if(cnt 0) ret root.val;dfs(root.right);}
}6.⼆叉树的所有路径
链接: https://leetcode.cn/problems/binary-tree-paths/ 分析: 明确接口的作用:给你一个根节点,给我拼接上左子树和右子树 函数头: 需要提供一个根节点和走到当前节点之前已经拼接好的字符串(path) 函数体:先创建出一个新的字符串用于接受path,接着以这个新的字符串为基准,遍历左子树和右子树 递归出口:当root为叶子节点时,证明一个完整的二叉树路径已经被拼接完毕,让ret添加这个拼接完毕的字符串路径即可
代码:
class Solution {ListString ret new ArrayList();// 返回值public ListString binaryTreePaths(TreeNode root) {dfs(root,new StringBuffer());return ret;}private void dfs(TreeNode root,StringBuffer path) {StringBuffer newPath new StringBuffer(path);newPath.append(Integer.toString(root.val));if(root.left null root.right null) {ret.add(newPath.toString());return;}newPath.append(-);if(root.left ! null) dfs(root.left,newPath);if(root.right ! null) dfs(root.right,newPath);}
}
