代码随想录算法训练营第二十天 | Java |530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先
1 530. 二叉搜索树的最小绝对差
题目：给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
提示：
- 树中节点的数目范围是
[2, 104] 0 <= Node.val <= 105
思路：根据二叉搜索树的性质可知，中序遍历后得到一个不重复的单调递增数组，对该数组进行差值比较即可得到最小差值。
升级思路：中序遍历时，记录前一个遍历节点的值，得到当前节点与前一个节点的差值，更新得到最小差值，本思路只需要遍历一次二叉树即可。
注意： 升级思路中，遍历第一个节点时要根据前一个节点pre是否为空进行判断。
Java实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int minDiff = Integer.MAX_VALUE;
TreeNode pre ;
public int getMinimumDifference(TreeNode root) {
inOrder(root);
return minDiff;
}
private void inOrder(TreeNode root){
if(root == null){
return ;
}
inOrder(root.left);
if(pre !=null){
minDiff = Math.min(minDiff,root.val-pre.val);
}
pre = root;
inOrder(root.right);
}
// ArrayList<Integer> point = new ArrayList<Integer>();
// public int getMinimumDifference(TreeNode root) {
// inOrder(root);
// return minDifference(point);
// }
// private void inOrder(TreeNode root){
// if(root == null){
// return ;
// }
// inOrder(root.left);
// point.add(root.val);
// inOrder(root.right);
// }
// private int minDifference(ArrayList<Integer> point){
// int min = point.get(point.size()-1);
// for(int i = point.size() -1;i>0;i--){
// if(point.get(i)-point.get(i-1)<min){
// min = point.get(i)-point.get(i-1);
// }
// }
// return min;
// }
}2 501. 二叉搜索树中的众数
题目： 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。如果树中有不止一个众数，可以按 任意顺序 返回。假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
提示：
- 树中节点的数目在范围
[1, 104]内 -105 <= Node.val <= 105
思路：最直接的做法是遍历二叉树，将节点值和出现次数加入map中，对map中元素排序得到结果。
升级思路：中序遍历二叉树，并在遍历过程中记录元素的出现次数，将出现次数最大的元素保存到res数组中记录下来。
注意：出现次数随着每次计数而刷新，当出现新的最大计数时，res中元素要清空并更新最大计数值。
Java实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
// 利用搜索二叉树特性，一次性遍历得出众数集合
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;
}
private 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){
maxCount = count;
resList.clear();
resList.add(rootValue);
}else if(count == maxCount){
resList.add(rootValue);
}
pre = root;
findMode1(root.right);
}
}3 236. 二叉树的最近公共祖先
题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
提示：
- 树中节点数目在范围
[2, 105]内。 -109 <= Node.val <= 109- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
思路：本题从下向上寻找比较方便，确定p和q的子树后找到他们的离他们最近的共同祖先，即深度最大的公共祖先。采用后续遍历的方法，左右中，逻辑上的从下至上。当找到p或q时，返回找到的节点，若都找到时，就可以返回公共祖先。
注意：公共祖先可以为q或p自身，因此在判断时，root为空或者root等于q或者root等于p要可以返回root。
Java实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode 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;
}
if(left == null && right != null){
return right;
}
if(left != null && right == null){
return left;
}else{
return root;
}
}
}