算法训练营day21

2024-04-24 03:28

文章标签 算法训练营 day21

本文主要是介绍算法训练营day21，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、二叉搜索树的最小绝对差

参考链接530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

利用二叉搜索树的性质 + 中序遍历获取递增序列，还可以解决其他问题

173. 二叉搜索树迭代器 - 力扣（LeetCode）
530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）
230. 二叉搜索树中第K小的元素 - 力扣（LeetCode）
501. 二叉搜索树中的众数 - 力扣（LeetCode）
938. 二叉搜索树的范围和 - 力扣（LeetCode）
653. 两数之和 IV - 输入二叉搜索树 - 力扣（LeetCode）
getMinimumDifference方法是解决问题的关键方法。它接受一个TreeNode类型的参数root，表示二叉树的根节点。首先，通过调用inOrderTransfer方法，按照中序遍历的顺序将二叉树的节点值存储到list中。
然后，创建一个大小为list长度的整型数组a，将list中的元素赋值给数组a。接下来，使用一个变量min初始化为整型的最大值Integer.MAX_VALUE。然后，通过遍历数组a，计算相邻两个元素的差值，并将较小的差值更新到min中。
最后，返回min作为结果。

class Solution {List<Integer> list=new ArrayList<>();public int getMinimumDifference(TreeNode root) {inOrderTransfer(root);int[] a=new int[list.size()];for(int i=0;i<a.length;i++){a[i]=list.get(i);}int min=Integer.MAX_VALUE;for(int i=0;i<a.length-1;i++){min=Math.min(min, a[i+1]-a[i]);}return min;}private void inOrderTransfer(TreeNode root){if(root==null)return ;inOrderTransfer(root.left);list.add(root.val);inOrderTransfer(root.right);}
}

二、二叉搜索树中的众数

findMode方法：接受一个TreeNode类型的参数root，表示二叉树的根节点。在该方法中，首先对成员变量进行初始化。然后，调用findMode1方法进行中序遍历，寻找众数。接着，根据resList中的众数，创建一个整型数组res，并将其返回作为结果。
findMode1方法是一个递归方法，用于执行中序遍历操作。它接受一个TreeNode类型的参数root，表示当前子树的根节点。方法首先判断root是否为空，如果为空则直接返回。然后，递归调用findMode1方法，遍历左子树。
在遍历过程中，首先获取当前节点的值rootValue。然后，通过与前一个节点的值进行比较，判断当前节点值出现的次数。如果当前节点与前一个节点的值不同，说明出现了一个新的值，将计数count重置为1；否则，计数count加1。
接下来，根据计数count与最大计数maxCount的比较，更新众数的结果数组resList和最大计数maxCount。如果count大于maxCount，则清空resList并将当前节点值添加进去，并更新maxCount为count；如果count等于maxCount，则将当前节点值添加到resList中。最后，将当前节点作为前一个节点pre。

最后，递归调用findMode1方法，遍历右子树。

class Solution {ArrayList<Integer> 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);}
}

三、二叉树的最近公共祖先

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 该题用于记忆，DFS//解释题解终止条件中第三种情况中b情况，root == p 或者 root = q 说明当前树找到了p或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) return null; // 1.if(left == null) return right; // 3.if(right == null) return left; // 4.return root; // 2. if(left != null and right != null) 如果左右子树都不为空，返回root}
}