代码随想录算法训练营，9月14日 | 530.二叉搜索树的最小绝对差，501.二叉搜索树中的众数，236. 二叉树的最近公共祖先

530.二叉搜索树的最小绝对差
题目链接：530.二叉搜索树的最小绝对差
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰二叉搜索树的最小绝对差
日期：2024-09-14

想法：好好利用二叉搜索树中序遍历是有序的性质，设置一个节点表示前一个结点就能很方便的计算差值了
Java代码如下：

class Solution {
    int res = Integer.MAX_VALUE;
    TreeNode pre;
    public void travel(TreeNode root){
        if(root == null) return;
        travel(root.left);
        if(pre != null){
            res = Math.min(res, root.val - pre.val);
        }
        pre = root;
        travel(root.right);
    }

    public int getMinimumDifference(TreeNode root) {
        travel(root);
        return res;
    }
}

总结：root.val - pre.val是一定为非负的，所以不需要取绝对值操作了。

501.二叉搜索树中的众数
题目链接：501.二叉搜索树中的众数
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰二叉搜索树中的众数
日期：2024-09-14

想法：二叉搜索树想到中序，还需要一个计数，以及一个记录最大的次数，当遍历第一个时计数为1，此后如果中序遍历的值与前一个（这里也需要pre）不同，计数重置为1，除此之外就只会是当前值与上一个值相等，所以count计数加一，接着还需要判断此时这个数是不是最大的，如果是最大的，将原本列表中的数清空（之前的最大数量的数已经不再是最大数量了），加入此时这个数root.val,再更新最大数量maxCount，操作完毕该进入下一个节点，所以需要将此时的root记录为pre，最后在递归右边，完成中序遍历。
Java代码如下：

class Solution {
    TreeNode pre;
    ArrayList<Integer> res;
    int count;
    int maxCount;
    public void findMode1(TreeNode root){
        if(root == null) return;
        findMode1(root.left);
        if(pre == null || root.val != pre.val){
            count = 1;
        }else{
            count++;
        }
        if(count > maxCount){
            res.clear();
            res.add(root.val);
            maxCount = count;
        }else if(count == maxCount){
            res.add(root.val);
        }
        pre = root;
        findMode1(root.right);
    }
    public int[] findMode(TreeNode root) {
        pre = null;
        maxCount = 0;
        res = new ArrayList<>();
        findMode1(root);
        int[] result = new int[res.size()];
        for(int i = 0; i < result.length; i++){
            result[i] = res.get(i);
        }
        return result;
    }
}

236. 二叉树的最近公共祖先
题目链接：236. 二叉树的最近公共祖先
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰二叉树的最近公共祖先
日期：2024-09-14

Java代码如下：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == q || root == p){//包含了两种情况，一是pq不为其中之一的祖先，另一是p为q祖先或反之
            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 right;
        }else if(left != null && right == null){//这两步巧在返回的就是最近公共祖先了
            return left;
        }else{
            return root;
        }
    }
}