周末有事，将后面两天的题提前刷了
530. 二叉搜索树的最小绝对差
List<Integer> list = new ArrayList<>();
public int getMinimumDifference(TreeNode root) {
// 二叉搜索树，求最小差值
getPreTreeNode(root);
// 已知节点个数>=2
// 相邻的两个数相减才会有最小差值
int minValue = Integer.MAX_VALUE;
for (int i = 1; i < list.size(); i++) {
int sub = list.get(i) - list.get(i - 1);
minValue = Math.min(sub, minValue);
}
return minValue;
}
private void getPreTreeNode(TreeNode root) {
if (root == null) {
return;
}
getPreTreeNode(root.left);
list.add(root.val);
getPreTreeNode(root.right);
}
二叉搜索树的中序遍历是一个从小到大的有序数组
既然是有序数组，那么最小值必然是相邻两个元素的差值
501. 二叉搜索树中的众数
private Map<Integer, Integer> map = new HashMap<>();
public int[] findMode(TreeNode root) {
if (root == null) {
return null;
}
getPreTreeNode(root);
List<Integer> list = new ArrayList<>(map.size());
int maxSize = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
maxSize = entry.getValue() > maxSize ? entry.getValue() : maxSize;
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == maxSize) {
list.add(entry.getKey());
}
}
return list.stream().mapToInt(i -> i).toArray();
}
private void getPreTreeNode(TreeNode root) {
if (root == null) {
return;
}
getPreTreeNode(root.left);
map.put(root.val, map.getOrDefault(root.val, 0) + 1);
getPreTreeNode(root.right);
}
这是一个有重复数据的二叉搜索树，那么中序遍历也会是一个有序数组
将遍历数据放入map中，个数就统计出来了，根据个数，进行判断最大的次数是多少个,最后进行结果输出
236. 二叉树的最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root.val == p.val || root.val == q.val) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null && right == null) {
return null;
} else if (left != null && right != null) {
return root;
} else if (right != null) {
return right;
} else {
return left;
}
}
该题找最近公共祖先，所有节点的值都是唯一的，p、q 为不同节点且均存在于给定的二叉树中。（题目给出）
有三种情况：
二叉树：
[1,2,3]
p:2,q:3p在左子树，q在右子树,有一个共同父节点1.
二叉树[1,null,2,null,null,3,4]
p:2,q:3p是父节点.
二叉树[1,2,null,3,4]
p:1,q:2q是父节点.
遍历整个二叉树，当碰到p,q节点即返回
对左节点和右节点进行比较，
- 如果都为空，说明该节点没找到
- 如果都不为空，说明该节点就是父节点
- 如果某一个节点不为空，返回该节点（会返回到开始节点，说明这两个节点都在同一个树上）
