一、二叉搜索树的最小绝对差
参考链接530. 二叉搜索树的最小绝对差 - 力扣(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++;
}
// 更新结果以及maxCount
if (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
}
}