wordpress建站 防攻击,江苏泰州seo网络优化推广,网站建设方案行业,wordpress添加文件2m530.二叉搜索树的最小绝对差
题目链接
https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/
题目描述 思路
遇到在二叉搜索树上求什么最值#xff0c;求差值之类的#xff0c;都要思考一下二叉搜索树可是有序的#xff0c;要利用好这一特点。…530.二叉搜索树的最小绝对差
题目链接
https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/
题目描述 思路
遇到在二叉搜索树上求什么最值求差值之类的都要思考一下二叉搜索树可是有序的要利用好这一特点。二叉树的中序遍历是从小到大的顺序
1、中序遍历
先中序遍历得到二叉搜索树的有序数组再遍历一遍数组找到最小差值
class Solution {public int getMinimumDifference(TreeNode root) {int min Integer.MAX_VALUE;ListInteger list new ArrayList();midorder(root,list);for (int i 1; i list.size(); i) {min Math.min(min,list.get(i)-list.get(i-1));}return min;}private static void midorder(TreeNode root,ListInteger list){if(rootnull) return;midorder(root.left,list);list.add(root.val);midorder(root.right,list);}
}2、双指针 class Solution {TreeNode pre;// 记录上一个遍历的结点int result Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {if(rootnull)return 0;traversal(root);return result;}public void traversal(TreeNode root){if(rootnull)return;//左traversal(root.left);//中if(pre!null){result Math.min(result,root.val-pre.val);}pre root;//右traversal(root.right);}
}501.二叉搜索树中的众数
题目链接
https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
题目描述 思路
将每个节点以及节点出现的次数存放到map集合中遍历集合的值找到最大的即出现次数最多的再找到出现次数为最大值的所有键
class Solution {public int[] findMode(TreeNode root) {MapInteger,Integer map new HashMap();midorder(root,map);int maxValue 0;//找出出现次数最多的值for (Integer value : map.values()) {maxValue Math.max(maxValue,value);}//找到出现次数最多对应的键值//创建一个数组存放出现次数最多的值ListInteger list new ArrayList();for (Integer integer : map.keySet()) {if(map.get(integer)maxValue){list.add(integer);}}int[] arr new int[list.size()];for (int i 0; i list.size(); i) {arr[i] list.get(i);}return arr;}private void midorder(TreeNode root, MapInteger,Integer map){if(rootnull) return;midorder(root.left,map);map.put(root.val, map.getOrDefault(root.val,0)1);midorder(root.right,map);}
}思路2
findMode1函数中按照中序遍历去进行判断pre为空即刚开始或者pre当前节点值说明已经开始计算下一个节点的出现次数了的时候都将count置为1 只有pre当前节点值的时候才将count加加 接下来去判断count和maxCount刚开始会把一些无关的都添加到列表中但是在比较的过程中会不断的更新maxCount所以需要清空列表去添加最大的最后在主函数中调用这个函数再用数组去存储
class Solution {ArrayListInteger resList;int maxCount;int count;TreeNode pre;public int[] findMode(TreeNode root) {resList new ArrayList();maxCount 0;count 0;pre null;findMode1(root);int[] res new int[resList.size()];for (int i 0; i resList.size(); i) {res[i] resList.get(i);}return res;}public void findMode1(TreeNode root) {if (root null) {return;}findMode1(root.left);int rootValue root.val;// 计数if (pre null || rootValue ! pre.val) {count 1;} else {count;}// 更新结果以及maxCountif (count maxCount) {resList.clear();resList.add(rootValue);maxCount count;} else if (count maxCount) {resList.add(rootValue);}pre root;findMode1(root.right);}
}236. 二叉树的最近公共祖先
题目链接
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
题目描述 思路
没太明白
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root null || root p || root q) { // 递归结束条件return root;}// 后序遍历TreeNode left lowestCommonAncestor(root.left, p, q);TreeNode right lowestCommonAncestor(root.right, p, q);if(left null right null) { // 若未找到节点 p 或 qreturn null;}else if(left null right ! null) { // 若找到一个节点return right;}else if(left ! null right null) { // 若找到一个节点return left;}else { // 若找到两个节点return root;}}
}
