530.二叉搜索树的最小绝对差
需要领悟一下二叉树遍历上双指针操作，优先掌握递归
视频讲解：https://www.bilibili.com/video/BV1DD4y11779
class Solution {
int minDiff = Integer.MAX_VALUE; // 初始化为最大整数，确保任何实际值都比它小
// TreeNode pre = null;
public int getMinimumDifference(TreeNode root) {
if (root == null) {
return Integer.MAX_VALUE;
}
// 先处理左子树
int leftMinDiff = getMinimumDifference(root.left);
// 处理当前节点
if (pre != null) {
minDiff = Math.min(minDiff, root.val - pre.val); // 更新最小差值
}
pre = root;
// 返回当前节点与左子树的最小差值
int currentMinDiff = minDiff;
// 处理右子树
int rightMinDiff = getMinimumDifference(root.right);
// 返回左子树、右子树和当前节点三者之间的最小差值
return Math.min(currentMinDiff, Math.min(leftMinDiff, rightMinDiff));
}
TreeNode pre = null; // 初始化为 null
}
class Solution {
TreeNode pre = null;
int min = Integer.MAX_VALUE;
public void getMin(TreeNode root){
if(root == null) return;
getMin(root.left);
if(pre != null){
min = Math.min(min, root.val - pre.val);
}
pre = root;
getMin(root.right);
}
public int getMinimumDifference(TreeNode root) {
getMin(root);
return min;
}
}
501.二叉搜索树中的众数
和 530差不多双指针思路，不过 这里涉及到一个很巧妙的代码技巧。
可以先自己做做看，然后看我的视频讲解。
视频讲解：https://www.bilibili.com/video/BV1fD4y117gp
236. 二叉树的最近公共祖先
本题其实是比较难的，可以先看我的视频讲解
视频讲解：https://www.bilibili.com/video/BV1jd4y1B7E2
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
if(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 root;
if(left != null) return left;
if(right != null) return right;
if(left == null && right == null) return null;
return root;
}
}
